Find recurrence equation from algorithm
I have to find the recurrence equation from this algorithm:
ALGO(n)
if n <= 2 then return(0)
else
y = ALGO(n/3)
i = 2^n
while i >= 2 do
j = (1/2) * log(i) //base 2
while j > 0 do
i = i/2
j = j - 1
z = ALGO(n/2)
return(z+y)
I reasoned about it and concluded that T(n) = O(1) if n<=2
I think that the inner while is an O(n) (j is decreased by 1 at e开发者_如何学Goach iteration) while the outer while is an O(logn) (the i is halved at each iteration), giving an O(n*log(n)):
T(n) = T(n/3) + T(n/2) + O(n*log(n)) if n > 2
Is this a good argument?
The two while loop should be O(n):
1. i = 2^n;
2. j = (1/2) * log (i) = 1/2 * n = n/2
3. the inner while executes for n/2 times then j becomes 0, now i = i / 2^(n/2) = 2^(n/2);
Now this program will go back to step 1, only with i halved. So the two loops should be:
n/2+n/4+n/8+... = O(n)
In fact this could also be viewed from a simpler perspective. Since the loop won't terminate until i == 1, and for every execution i = i / 2, the inner loop will run n times. Imagine we flatten the inner loop and the out loop, there will be n times of i = i / 2, hence the two loops are O(n).
In conclusion, T(n) = T(n/3) + T(n/2) + O(n).
Hope this could be helpful!
精彩评论