Solving recurrence relation with different rules for odd and even n 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 &gt; \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?
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)$.