patternMinor
Solution to recurrence $T(n) = T(n/2) + n^2$
Viewed 0 times
solutionrecurrencestackoverflow
Problem
I am getting confused with the solution to this recurrence -
$T(n) = T(n/2) + n^2$
Recursion tree -
So it turns out to be -
$T(n) = n^2(1 + 1/4 + (1/4)^2) + \ldots (1/4)^{\log_2 n - 1})$
$T(n) = 4*n^2(1- (1/4)^{\log_2 n})/3 + n^2 $
$T(n) = 4*n^2(1 - 1^{\log_2 n} + 4^{\log_2 n})/3 + n^2 $
$ T(n) = 4*n^2(1 - 1 + n^{\log_2 4})/3 + n^2$
$ T(n) = 4*n^2(n^2)/3 + n^2$
$ T(n) = 4/3 * (n^4) + n^2 $
$ T(n) = \Theta(n^4) $
But according to the Master theorem, $a = 1, b = 2, f(n) = n^2 $, then $n^{\log_2 1} = 1 $ which is polynomial times less than $ n^2 $ so the solution should be $ \Theta (n^2) $?
$T(n) = T(n/2) + n^2$
Recursion tree -
T(n) Height lg n + 1
|
T(n/2)
|
T(n/4)So it turns out to be -
$T(n) = n^2(1 + 1/4 + (1/4)^2) + \ldots (1/4)^{\log_2 n - 1})$
$T(n) = 4*n^2(1- (1/4)^{\log_2 n})/3 + n^2 $
$T(n) = 4*n^2(1 - 1^{\log_2 n} + 4^{\log_2 n})/3 + n^2 $
$ T(n) = 4*n^2(1 - 1 + n^{\log_2 4})/3 + n^2$
$ T(n) = 4*n^2(n^2)/3 + n^2$
$ T(n) = 4/3 * (n^4) + n^2 $
$ T(n) = \Theta(n^4) $
But according to the Master theorem, $a = 1, b = 2, f(n) = n^2 $, then $n^{\log_2 1} = 1 $ which is polynomial times less than $ n^2 $ so the solution should be $ \Theta (n^2) $?
Solution
Try this way:
$$
\begin{align*}
T(n) &= T(n/2) + n^2 \\
T(n) &= T(n/4) + (n/2)^2 + n^2\text{ (expand $T(n/2)$)} \\
T(n) &= T(n/8) + (n/4)^2 + (n/2)^2 + n^2\text{ (expand $T(n/4)$)}
\end{align*}
$$
You will end up with:
$$
\begin{align*}
T(n) &= n^2 + (n/2)^2 + (n/4)^2 + (n/8)^2 + \cdots + (n/2^{\lg n})^2 \\
T(n) &= n^2 + n^2/4 + n^2/16 + n^2/64 + \cdots
\end{align*}
$$
We can bound this from above as $T(n) \le 2 n^2$ and from below with $T(n) \ge n^2$, giving $T(n) = \Theta(n^2)$.
Note: we do not need to use induction to prove this; since we can create an upper bound of $T(n) \le c_1f(n)$ and a lower bound of $T(n) \ge c_2f(n)$, we can use the definition of $\Theta(n)$ to establish the time complexity of the relation.
$$
\begin{align*}
T(n) &= T(n/2) + n^2 \\
T(n) &= T(n/4) + (n/2)^2 + n^2\text{ (expand $T(n/2)$)} \\
T(n) &= T(n/8) + (n/4)^2 + (n/2)^2 + n^2\text{ (expand $T(n/4)$)}
\end{align*}
$$
You will end up with:
$$
\begin{align*}
T(n) &= n^2 + (n/2)^2 + (n/4)^2 + (n/8)^2 + \cdots + (n/2^{\lg n})^2 \\
T(n) &= n^2 + n^2/4 + n^2/16 + n^2/64 + \cdots
\end{align*}
$$
We can bound this from above as $T(n) \le 2 n^2$ and from below with $T(n) \ge n^2$, giving $T(n) = \Theta(n^2)$.
Note: we do not need to use induction to prove this; since we can create an upper bound of $T(n) \le c_1f(n)$ and a lower bound of $T(n) \ge c_2f(n)$, we can use the definition of $\Theta(n)$ to establish the time complexity of the relation.
Context
StackExchange Computer Science Q#19318, answer score: 5
Revisions (0)
No revisions yet.