Week 2 Algorithms Optional problem 1

Problem

1. Give the best upper bound that you can on the solution to the following recurrence: T(1)=1 andT(n)≤T([n√])+1 for n>1. (Here [x] denotes the "floor" function, which rounds down to the nearest integer.)

My answer
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))