recurrencemaster-theorem

Solve Recurrence for T(n) = 7T(n/7) + n

I'm trying to solve the recurrence for T(n) = 7T(n/7) + n. I know using Master Theorem it's O(nlog7n), but I want to solve it by substitution.

At level i, I get: 7^i T(n/7^i) + (n+7n+7^2n+ .... + 7^i n) By setting i = log7n, the above becomes: 7^(log7n)*T(1) + (n + 7n + 7^2n ..... + 7^(log7n) n

Since 7^log7n = n, the above finally becomes n+ (n+7n+(7^2)n+ ....n*n) This solves to O(n^2) to me not O(nlog7n), any idea what's wrong?

Solution 
  • T(n)=7T(n/7)+n=7[7T(n/72)+n/7]+n=72T(n/72)+2n=...=7kT(n/7k)+kn
n/7k=c ⇒ k=O(logn)
⇒T(n)=O(nlogn)