What is the time complexity of the next function?
int DoSomething(int n) {
if(n < 2) return 1;
else return DoSomething(floor(sqrt(n))) + n;
}
In my opinion the appropriate repetition would be:
The solution to this problem ...
Input 
The function becomes
Can you check and fix the solution?
you are right upto : -
S(m) = O(log(m))
then
T(2^m) = O(log(m))
n = 2^m
T(n) = O(log(m))
but m = log(n)
hence
T(n) = log(log(n))
Your conclusion is wrong in the first step!
Now, after going through your steps, your recurrent equation is wrong.
The recurrent will be ---> T(n) = a ⋅ T(n / b) + f(n)
, here: a = 1, b = 2 and f (n) = log n (since n is sequentially stored on the stack and decrements each time by half, whereas you assumed f (n) to be 1 // THIS IS THE SOURCE OF THE ERROR!
T(2^m)=T(2^(m/2))+m
// Refine your steps.
S(m)=S(m/2)+log m
// Improve your steps
When solving this equation using master theorem
--- it will fall under the second formula of the main theorem as
f (n) ~ = log n ~ = 1 == 0 (n ^ log 2 (1)) == 0 (n ^ 0) == 1 //, most important step, if not clear please ask ...
you will get solution like 0(log (m)).
S(m) = O(log m)
Then, when increasing to power T(2^(m))=O(log m)
, which will then give
Now, replacing the value of m as (m=log 2 (n))
back in this equation, you get
T(n)=O(log ( log (n)))
...
I hope this is very clear. Feel free to comment if you cannot understand a step ...
You can rely on a methodology like this to solve this problem:
