What is the worst case time complexity of the following recurrence relation?
T(n)=T(n/2)+T(n/4)+T(n/8)+n
- Θ(nlogn)
- Θ(n2)
- Θ(n)
-----------------------------------------------------------------------------------------------------------------------------------------------
i am solving like this
T(n) < 3*T(n/2) + n (because n/2 is largest of n/4 and n/8)
from masters'theorem,its T(n) will be theta(n^3 base 2) but that is equal to n^1.58 =O(n^1.58)
so,this is not giving O(n) which is the answer..what is wrong in this approach..??by tree method,i will get O(n).but whats wrong with this?
please clear ths.