CODEWITHSUNDEEP
algorithmrecursionbig-o
Programmer
Programmer

Reputation: 161

How to solve T(n) = 5T(n/2) + n^2, T(1) = 2 recursively

How to fond the asymptotic upper bound for T(n) = 5T(n/2) + n^2, T(1) = 2 without using master theorem.

Here are my steps, but I don't know how to deal with the summation at the end and thus cannot find the big-O answer for this recursion function.

T(n) = 5T(n/2) + n^2
     = 5^2 T(n/2^2) + 5(n/2)^2 + n^2
     = 5^3 T(n/2^3) + 5^2(n/2^2)^2 + 5(n/2)^2 + n^2
     = ...
     = 5^i T(n/2^i) + 5^i(n/2^i)^2 + ...+ 5^2(n/2^2)^2 + 5(n/2)^2 + n^2
     = 5^i T(n/2^i) + n^2 Sum of k from 0 to i, (5/4)^k

How to deal with the summation? Thanks.

Upvotes: 4

Views: 2149

Answers (1)

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 476584

How to deal with the summation?

What you describe here in the sum is a geometric progression [wiki]. Such sum of the form:

 n
---
\     i
/    a
---
i=0

has a known solution:

 n
---           n+1
\     i      a    - 1
/    a     = --------
---            a - 1
i=0

So here your sum:

Sum of k from 0 to i, (5/4)^k

is equal to:

4 * ((5/4)^(i+1) - 1)

We know that i is limited to log2n, and this should be sufficient to solve the equation.

Upvotes: 3

Related Questions