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(n\log_7n)$, but I want to solve it by substitution method.
At level $i$, I get: $7^i T(n/7^i) + (n+7n+7^2n+ \cdots + 7^i n)$
By setting $i = \log_7n$, the above becomes:
$$7^{\log_7n}\cdot T(1) + (n + 7n + 7^2n + \cdots + 7^{\log_7n}n$$
Since $7^{\log_7n} = n$, the above finally becomes
$$n+ (n+7n+(7^2)n+ \cdots + n\cdot n)$$
This solves to $O(n^2)$ to me since $n\cdot n$ dominates, not $O(n\log_7n)$, any idea what's wrong?
Here is what I get:
\begin{align}
T(n) &amp;= n + 7T(n/7) \\ &amp;= n + 7(n/7) + 7^2 T(n/7^2) \\ &amp;= n + 7(n/7) + 7^2(n/7^2) + 7^3 T(n/7^3)
\end{align}
and so on. Each of the summands equals $n$, and there are $O(\log n)$ of them.