patternMinor
Solving recurrence relation with different rules for odd and even n
Viewed 0 times
solvingevenwithrecurrencedifferentforandrulesrelationodd
Problem
Assume $T(1) = 1$, and
-
$T(n) = 2T(n/2) + n^2$ for even $n$,
-
$T(n) = T(n − 1) + n$ for odd $n$.
I'm new of learning to solve recurrence problem, for 1, it seems we can apply Master Theorem directly and we got $a = 2$, $b = 2$, $d = 2$, therefore it's the case that $d > \log_b(a)$ and $T(n) = \Theta(n^2)$.
But I'm unsure for the given $n$ is even, does this effect to our final result?
Because I noticed on the second one, for odd $n$ it changed our result from $\Theta(n^2)$ to $\Theta(n)$. Suppose we have
$T(n) = T(n − 1) + n$, we can solve as summation from $0$ to $n$ such $0 + 1 + 2 + \dots + n - 1 + n = n(n+1)/2$, and hence $\Theta(n^2)$. However, if for odd $n$, I'm thinking this naively, we can just sum all odd numbers in the sequence so we have $1 + 3 + 5 + \dots + n = 2n-1$ and hence $\Theta(n)$. Is my assumption accurate?
-
$T(n) = 2T(n/2) + n^2$ for even $n$,
-
$T(n) = T(n − 1) + n$ for odd $n$.
I'm new of learning to solve recurrence problem, for 1, it seems we can apply Master Theorem directly and we got $a = 2$, $b = 2$, $d = 2$, therefore it's the case that $d > \log_b(a)$ and $T(n) = \Theta(n^2)$.
But I'm unsure for the given $n$ is even, does this effect to our final result?
Because I noticed on the second one, for odd $n$ it changed our result from $\Theta(n^2)$ to $\Theta(n)$. Suppose we have
$T(n) = T(n − 1) + n$, we can solve as summation from $0$ to $n$ such $0 + 1 + 2 + \dots + n - 1 + n = n(n+1)/2$, and hence $\Theta(n^2)$. However, if for odd $n$, I'm thinking this naively, we can just sum all odd numbers in the sequence so we have $1 + 3 + 5 + \dots + n = 2n-1$ and hence $\Theta(n)$. Is my assumption accurate?
Solution
When $n$ is odd, the recurrence can be unrolled:
$$
T(n) = T(n-1) + n = 2T\left(\frac{n-1}{2}\right) + (n-1)^2 + n.
$$
In total, we always have
$$
T(n) = 2T(\lfloor n/2 \rfloor) + \Theta(n^2).
$$
Applying the master theorem, we conclude that $T(n) = \Theta(n^2)$.
$$
T(n) = T(n-1) + n = 2T\left(\frac{n-1}{2}\right) + (n-1)^2 + n.
$$
In total, we always have
$$
T(n) = 2T(\lfloor n/2 \rfloor) + \Theta(n^2).
$$
Applying the master theorem, we conclude that $T(n) = \Theta(n^2)$.
Context
StackExchange Computer Science Q#116674, answer score: 2
Revisions (0)
No revisions yet.