Recurrence Relations and drawing Recursion trees
Here is the algorithm
Algorithm Mystery(A: Array [i..j] of integer) i & j are array starting and
ending indexes
if i=j then return A[i]
else
k=i+floor((j-i)/2)
temp1= Mystery(A[i..k])
temp2= Mystery(A[(k+1)..j]
if temp1<temp2 then return temp1 else return temp2
I believe the complexity is: T(1) = c T(n) = 2T(n/2) + n
but from here I'm not sure where to go all the examples have the second
equation ending with cn so i have no idea how to draw the tree. Did i
solve the recursion wrong? I just need some help getting on the right
direction.
No comments:
Post a Comment