What is the approach to solving a recurrence when I have more than one periodic function call the right side of the equation?
I am trying to analyze the complexity of a function call PEL (A [1..n]), where n is some power of 3, and PEL is determined by the following algorithm:
function PEL(A[m..n]){
if(n - m <= 1) return 1;
else {
p := [(n - m + 1)/3];
MAKE(A[m..n]);
PEL(A[m..n + p - 1]); PEL(A[m + p .. m + 3p - 1]);
}
}
The complexity of MAKE (A [m..n]) is theta ((nm) log (nm)).
From what I've gathered so far, we are dealing with the following recurrence relation:
C(N) = C(N/3) + C(2*N/3) + theta( (n-m)log(n-m) )
Where
C(1) = C(2) = 1
I understand that we need to apply the main theorem here , but in the main theorem we have recurrence relations of the form:
C(N) = a * C(N/b) + f(n)
And I have no idea how to get rid of the second repeated C () call in my recurrent relationship, so how do I do that? I don't know how to get the a and b values .
+3
source to share
1 answer
Like all commentators, I need to use the Akra-Bazzi theorem.
C(1) = 1
C(2) = 1
For N > 2 we need to first find 'p' from the following equation :
(1/3)^p + (2/3)^p = 1. It is obvious that p = 1.
Next we need to solve N^p * ( 1 + I[1,N](log(u)/u) ) with p = 1
I[1,N](x) denotes the integral of x, from 1 to N.
also I wrote log(u)/u instead of (u - 1)log(u-1)/u^2
since I((u-1)log(u-1)/u^2) looks like a monster.
I[1,N](log(u)/u) gives log^2(N)/2 so the end result is N + N*(log^2(N)/2).
All in all, the running time = theta( N + N*(log^2(N)/2) ).
0
source to share