Would much appreciate someone explaining how they managed to get to the upper bound of this algorithm.$$T(n) = 2T(\lfloor \sqrt n\rfloor) + ln (n)$$$$T(1) = 0$$Solution is given as:$$T(n) = O(logn*log(log(n)))$$
Upper bound of algorithm with flooring
algorithms;algorithm analysis;recursion
If a number is of the form $n = 2^{2^k}$ then you never encounter the floor as you open up the recursion, and then there is no problem. If you're interested in a general upper bound, you can prove by induction that $T(n)$ is monotone in $n$: if $n \leq m$ then $T(n) \leq T(m)$. Now given $n$, find some $m \leq n^2$ which is of the form $2^{2^k}$, and then$$ T(n) \leq T(m) = O(\log m \log\log m) = O(\log n \log\log n). $$