Time Complexity

Question

What is the running time of following recurrence relation?

T(n) = T(n/2) + T(n/4) + T(n/8) + n

Answer 1

using recurrence tree method ans is theta(n). 


 

Answer 2

Can be written as T(n) = T(n/2)  + theta(n).
T(n) = n + n/2 +n/4 + n/8.........
T(n) = n(1 + 1/2 +1/4......).
T(n) = n*1.
T(n) = theta(n)

Comments

Why have you ignored the T(n/4) and T(n/8)

---

Because the computation time taken by them is less in comparison to T(n/2), so we can neglect them to get the got idea.