CODEWITHSUNDEEP
algorithmrecursion
Chayakay
Chayakay

Reputation: 31

how to solve a iterative substitution equation?

So I'm struggling with a question, I need to find the time complexity of this equation using iterative substitution, Now I understand how to expand the equation however I do not know how to find the time complexity using it. I know the answer is o(n^log2 3).

T(n) = 3T(n/2) + O(n)

I've expanded from about here, what do I do next?

3^3T(n/2^3) + 3^2(n/2^2) + 3n/2 + n

What do I do next to reach the answer of o(n^log2 3)?
Can someone please explain this to me step by step?

Upvotes: 0

Views: 127

Answers (1)

SomeDude
SomeDude

Reputation: 14228

It can be solved like this:

T(n) = 3T(n/2) + O(n)

     = 3(3T(n/4) + O(n/2)) + O(n)

     = 3^2(T(n/4)) + O(n)

     = 3^4(T(n/8)) + O(n)

Note O(n/4) + O(n/2) + O(n) is still O(n)

let n = 2^k

then T(n) = 3^(k-1) + O(n)

          = 3^(log(n) - 1 ) + O(n) // log(n) is log (n) to base 2

          = O( n^log(3) ) because n^log(3) > n

Upvotes: 1

Related Questions