Problem
At jth level:
Work done in combine step = 1
Number of sub-problems = 1
Thus the only thing needed to find out is depth of the recursion tree.
To find out depth:
Represent n as 2^(lgn). After k recursions, the size of the subproblem will be n^(1/2^k) = 2^(lgn/2^k). You want this to be small enough for the base case, i.e. say smaller than 2.
Then 2^(lgn/2^k) = 2
==> lgn/2^k = 1
==> lg n = 2^k
==>k = lg (lg n)
Thus the running time is O(lg(lg n))
- Give the best upper bound that you can on the solution to the following recurrence:
T(1)=1 andT(n)≤T([n√])+1 forn>1 . (Here [x] denotes the "floor" function, which rounds down to the nearest integer.)
At jth level:
Work done in combine step = 1
Number of sub-problems = 1
Thus the only thing needed to find out is depth of the recursion tree.
To find out depth:
Represent n as 2^(lgn). After k recursions, the size of the subproblem will be n^(1/2^k) = 2^(lgn/2^k). You want this to be small enough for the base case, i.e. say smaller than 2.
Then 2^(lgn/2^k) = 2
==> lgn/2^k = 1
==> lg n = 2^k
==>k = lg (lg n)
Thus the running time is O(lg(lg n))
No comments:
Post a Comment