recurence relation

Question

Which of the following represents most appropriate asymptotic solution for given reccurance:

(A) O(n)

(B) O(log n)

(C) O(log log n)

(D) O(log n)2

Comments

O(logn)

---

Please provide solution because I'm weak in this type of problem

---

take n=2^m

then, it become  T(2^m)= T(2^m/2)+m;

                          write it as S(m)=S(m/2)+m;

                        then apply master's theorem

                        b will be answer

Answer 1

T(n) = T( √n) + log₂ n   _____________    Eqⁿ 1

Let's take n = 2^m , taking log both side.

log₂ n = m log₂2 put in Eqⁿ 1.

T(2^m) = T(2^m/2) + log₂ 2^{m _____________} Eqⁿ 2   

[ ∵ log_b bⁿ = n ] using this we can rewrite Eqⁿ 2 as :

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

or

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

solve using MT we get, S(m) = O(m)

change the value of m to log₂n.

so TC is log₂n