I've been working on a problem set for a bit now and I seem to have gotten the master method down for recurrence examples. However, I find myself having difficulties with other methods (recurrence trees, substitution). here is the question I am stuck on: T(n) = T(n-2) + n^2 Is there a pattern as follows? n^2 + T(n-2) + T(n-4) +... where it goes until there is no more n left. so around n/2 times and would that mean that n^2 + (n-2)^2 + (n-i) ^2 so the asymptotic bound would be theta(n^2)??
I am honestly taking a shot in the dark here, so I was hoping someone could help guide me in how to approach these questions. perhaps not a direct answer to the question but a hint as to where I should begin would be best.
As you said, the result is going to be n^2 + (n-2)^2 + (n-4)^2 + ...
Intuitively you can feel that because there are a lot (n/2) elements in the sum, it's going to be more than O(n^2) - the same way as 1 + 2 + 3 + ... + n is more than O(n).
One way to prove it is that you can approximate the sum with half of the sum of all the square numbers, for which there is a formula. So it's Theta(n^3).