#made easy

Question

soluation for the recurrence relation is

f(x)=2T(floor(rootn))+logn

1.O(nlogloglogn)

2.O(nloglogn)

3.O(loglogn)

4O(lognloglogn)

Answer 1

$\\ T(n) = 2T( \sqrt n) + \log n \\ \\ take \ 2^k = n \\ \\ => T(2^{k}) = 2T(2^{\frac{k}{2}}) + \log (2^{k}) \\ \\ => S(k) = 2S(\frac{k}{2}) + k \\ \\ => using \ master \ theorem : S = O(k \log k) \\ \\ T(n) = O(\log n * \log (\log n)) = O(\log n \log \log n) \\$

Option 4

Note : Floor does not make any difference if n - > $\inf$

We can solve with recursion tree also

Comments

in this question what is the meaning of floor??