Problem Detail: Please help me calculate the time complexity of the following program.
int fun (int n) { if (n <= 2) return 1; else return fun(sqrt(n)) + n; } Please explain. There were four choices given.
- $Theta(n^2)$
- $Theta(n log n)$
- $Theta(log n)$
- $Theta(log log n)$
Asked By : Vishnu Vivek
Answered By : Farhad Yusufali
The running time of the function on an input $n$ can be expressed as: $$T(n) = T(sqrt n) + mathcal{O}(1)$$ which implies the running time of the function and the number of recursions differ only by a constant. The recursive chain ends when $n$ has been reduced to some value $k$, where $k le 2$. The number of recursions, $r$, can be expressed as: $$k^{2^r} = n implies r = log_2 log_k n$$ It follows that the running time is then: $$Theta(log_2 log_k n) = Theta(log log n)$$
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/6901
