Answer (B)
Let n = 2^m, T(n) = T(2^m)
Let T(2^m) = S(m)
>From the above two, T(n) = S(m)
S(m) = 2S(m/2) + C1
Above expression is a binary tree traversal recursion whose time
complexity is (m). You can also prove using Master theorem.
S(m) = (m)
= (logn) /* Since n = 2^m */
Now, let us go back to the original recursive function T(n)
T(n) = S(m)
= (Logn)
I din understand this.... its GATE 2006 Q...
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
