0

for a university course we’ve been tasked to solve a recurrence relation similar to the following:

$T(n) = T(n-4) + n$

We may assume that $T(1) = 1$, and that $T(k) = O(1)$.

I’ve tried solving both by unfolding and using a recurrence tree, but I get stuck with the base cases. From the recurrence tree it seems like the answer should be some kind of arithmetic series, but from unfolding I would expect an exponential with a linear component.

I’d appreciate seeing how a problem like this is solved so I can solve the assigned problem by myself!

Chickenmancer
  • 4,347
lh1395
  • 3
  • What makes you think the recurrence tree is arithmetic series and the unfolding is exponential. Can you show your work using MathJax or at least attaching images? – Sidharth Ghoshal Oct 05 '22 at 03:52
  • When you write $T(k) = O(1)$, it sounds like you mean $k \mapsto T(k)$ is a bounded function, but this cannot be since $T(n)-T(n-4) \to \infty$. Can you clarify what you mean by $T(k) = O(1)$? – Brian Moehring Oct 05 '22 at 03:59

1 Answers1

1

Note that $T(n) = T(n-4) + n$

Then tells us that (at least if n is a multiple of 4) that:

$$ T(n) = n + n-4 + (n-8) + ... T(0) $$

Now if we assume $T(0) = O(1)$ then we have that

$$ T(n) = n + (n-4) + (n-8) + ... O(1) $$

so we conclude that

$$ T(n) = \frac{n}{4} n + O(1) - 4 - 8 - 12 .... -n $$

Now at this point you can drop the terms on the right hand side but perhaps you are new and don't believe me so we can keep bashing this recurrence out

$$ T(n) = \frac{n}{4} n + O(1) - 4(1 + 2 + 3 ... \frac{n}{4}) $$

Now we go ahead and apply the formula that we know for sums of $1 ... n$ to find:

$$ T(n) = \frac{n^2}{4} + O(1) - 4 \frac{1}{2} \frac{n}{4} \left( \frac{n}{4} + 1 \right) $$

And this simplifies out to:

$$ T(n) = \frac{n^2}{4} + O(1) - \frac{n}{2} \left( \frac{n}{4} + 1 \right) = \frac{n^2}{4} + O(1) - \frac{n^2}{8} - \frac{n}{2}$$

Now those two quadratic terms combine but don't completely cancel out so you end up with a left over of:

$$ T(n) = \frac{n^2}{8} - \frac{n}{2} + O(1) $$

But we ignore the linear and lower terms and even forget the constant in front of the $n^2$ to just write

$$ T(n) = O(n^2) $$

Sidharth Ghoshal
  • 16,771