HiveBrain v1.2.0
Get Started
← Back to all entries
debugMinor

Error solving the next recurrence: $T(n)=7T(n/2)+n^2$

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
solvingerrortherecurrencenext

Problem

Hello I'm trying to solve this recurrence with the method that says the teacher that when you get to
\begin{align*}
T\bigg(\frac{n}{2^{k}} \bigg)
\end{align*} you do
\begin{align*}
\frac{n}{2^{k}} &= 1 \qquad (\text{by definition})\\
k &= \log_{2}(n)
\end{align*}

\begin{align*}
T(n) &= 7T(n/2) + n^2 \\ &= 7^2T(n/2^2) + 7(n/2)^2 + n^2 \\ &=
7^3T(n/2^3) + 7^2(n/2^2)^2 + 7(n/2)^2 + n^2 \\ &=\cdots \\ &=
7^{k}T\bigg(\frac{n}{2^{k}}\bigg) + \sum_{j=1}^{k-1} 7\frac{n}{2^{j}}+n^{2}\\ &=
7^{\log_{2}(n)} + \sum_{j=1}^{\log_{2}(n)-1} 7\bigg(\frac{n}{2^{j}}\bigg)^{2}+n^{2}\\
\end{align*}

After developing, I have left
\begin{align*}
7^{\log_{2}(n)}+n^{2}
\end{align*}
But I know the solution is
\begin{align*}
n^{\log_{2}(7)}
\end{align*}

What am I doing wrong?

Solution

Some of your sums have typos, but you already have the right answer.

Here's a useful fact about logarithms:

$a^{\lg b} = 2^{(\lg a) \cdot (\lg b)} = 2^{(\lg b) \cdot (\lg a)} = b^{\lg a}$

Apply it to your answer, keeping in mind that $\lg 7 \approx 2.8 > 2$:

$O(7^{\lg n} + n^2) = O(n^{\lg 7} + n^2) = O(n^{\lg 7})$

Context

StackExchange Computer Science Q#70835, answer score: 6

Revisions (0)

No revisions yet.