Recurrences

Question

What will be time complexity for both recurrences?

$$T(n) = \begin{cases}
2 \cdot T \left ( \sqrt n \right ) + \log n & \text{if } n > 4\\[1em]
1 & \text {if } n \leq 4
\end{cases}$$

$$T(n) = \begin{cases}
2 \cdot T \left ( \sqrt n \right ) + \frac{\log n}{\log \log n} & \text{if } n > 4\\[1em]
1 & \text {if } n \leq 4
\end{cases}$$

Answer 1

1) T(n) = 2T(n^1/2) + logn

   T(2^m) = 2 T(2^m/2) + m

S(m) = 2S(m/2) +m

putting in formula m^log2= m

So, complexity will be m log¹m = logn loglogn = O(logn. log²n)

2) T(n) = 2T(n^1/2) + (logn / loglogn)

   T(2^m) = 2 T(2^m/2) + m/logm

S(m) = 2S(m/2) + m/logm

Complexity will be O(logn. log³n)

Comments

Take S(m) = T($2^{m}$)

therefore, S(m) = 2S(m/2) + m

---

if S(m)=T(2^m)

then  it will be S(m)=2S(m^1/2)+m

bcoz T(2^m)=2T((2^m)^1/2)+m

---

I think you are confused. Let me help you with this.

if S(m) = T($2^{m}$)

then S(m/2) = T($2^{\frac{m}{2}}$) = T($\left ( 2^{m} \right )^{\frac{1}{2}}$

while S($m^{\frac{1}{2}}$) = T($2^{\sqrt m}$) which is not equal to T($2^{\frac{m}{2}}$). 

Laws of Indices.

I hope you understood now.