Question

What is the worst case time complexity of the following recurrence relation?
T(n)=T(n/2)+T(n/4)+T(n/8)+n

1.   Θ(nlogn)
2.   Θ(n2)
3.   Θ(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.

Comments

There is a good alternative for all these kind of problems which is AKRA-BAZZI METHOD which is basically generalization of Masters method. Its good to know about it

Ref: https://en.wikipedia.org/wiki/Akra%E2%80%93Bazzi_method

---

@Prajwal Bhat,

how we will apply Akra bazzi theorem here???

I solved it using Tree method as @Debashish Deka,

I got log₈n<=T(n)<=log₂n

as Time complexity.

But don't know how to solve it using Akra Bazzi theorem???

---

by tree method we will get O(8n) means O(n)

Answer 1

The no. of elements compared at each level are getting reduced in worst case as well which drives the complexity towards O(n) therefore the time complexity may not be computed by 3*T(n/2)+n because in this at each level the no. of elements get compared increases