# Formal mathematical resolution for Recurrence Relations

let's suppose we've got a simple Recurrence Relation: $$T(n) = \begin{cases} 1 & n=1 \\ T(n-1) + \Theta(n) & \text{otherwise} \end{cases}$$

At lesson we've resolved it, but I tried two other ways of resolution, and I would like to ask you if they're right and which, among all, is the most formal way to resolve it.

Method 1

Drawing the recurrence tree (whose each node has only one child), we see that its height is $$n$$ and each node receives as input $$n-i$$, where $$i$$ is its level. So each node costs $$\Theta(n-i)$$. Hence the total cost is $$T(n) = \sum_{i=0}^{n-1}\Theta(n-i)$$

Method 2

We see that the cost of each node is $$\Theta(n-i)$$ which is a $$\Theta(n)$$, so the total cost is $$T(n) = \sum_{i=0}^{n-1}\Theta(n)$$

Is what I did mathematically right? Even if in this example it looks trivial that it is right, then why when we have an algorithm that equally divides a problem in two equal-size subproblems (e.g. mergesort), the CLRS Book writes that each subproblem costs $$\Theta(\frac{n}{2^i})$$ but does not "simplify" it into $$\Theta(n)$$? So their final sum would be $$\sum_{i=0}^{h}\frac{n}{2^i}$$ and not $$\sum_{i=0}^{h}\Theta(n)$$ like I would do, since $$\Theta(\frac{n}{2^i}) \in \Theta(n)$$.

In this case it'd look like each node costs the same as its parent, which obviously can't be, but it is mathematically right.

Method 3

In Method 2 we said that each node costs locally $$\Theta(n)$$, and $$n$$ is the value we call the first recursive call with. But when $$n=1$$, its cost is $$1$$, so we should write $$T(n) = 1+\sum_{i=0}^{n-2}\Theta(n)$$

When $$n=2$$, its cost is $$\Theta(2) = \Theta(1)$$ and not $$\Theta(n)$$ (remember that this $$n$$ is the value of the first rec. call when we resolve the summation). But this would apply even when $$n=3, n=4, ...$$ So I'd write it as $$T(n) = \sum_{i=0}^{k}\Theta(1) + \sum_{i=1}^{n-k}\Theta(n)$$ meaning that there are a constant number of nodes that cost $$\Theta(1)$$ and the others cost depending on the value of $$n$$.

I do not know which one is the most formal way of resolving these relations. In all of these methods seem that there's something off, something not formal.

• It’s not true that $\Theta(n-i)=\Theta(n)$. May 20, 2022 at 8:55
• @YuvalFilmus, so sorry, $i$ is a constant, why ism't that an equivalence? I apologize if it is too trivial. May 20, 2022 at 9:34
• But $i$ is not constant - it could be as large as $n-1$. May 20, 2022 at 9:35
• With all methods $-i$ is irrelevant, in the formula the additive part is $\Theta(n)$, and you add it $n$ times. You probably have confused $T(n-1)$ with $T(n)-1$. May 21, 2022 at 15:36

Let me make the following suggestion: get rid of asymptotic notation.

Here is how to do that. Your recurrence relation is really the following: $$T(n) = \begin{cases} 1 & \text{if } n = 1, \\ T(n-1) + f(n) & \text{otherwise}, \end{cases}$$ where $$f(n) = \Theta(n)$$. Since $$f(n) = \Theta(n)$$, there are $$c,C,N > 0$$ such that $$cn \leq f(n) \leq Cn$$ for all $$n \geq N$$. If we assume that $$f(n) > 0$$ for all $$n$$, then we can assume that $$N = 1$$ (otherwise, the following needs to be slightly modified). Now define a new recurrence relation, depending on a parameter $$\gamma$$: $$T_{\gamma}(n) = \begin{cases} 1 & \text{if } n = 1, \\ T_\gamma(n-1) + \gamma n & \text{otherwise}. \end{cases}$$ A simple proof by induction shows that $$T_c(n) \leq T(n) \leq T_C(n)$$ for all $$n$$. Hence it suffices to analyze $$T_\gamma(n)$$. In fact, we can calculate $$T_\gamma(n)$$ exactly: $$T_\gamma(n) = 1 + \sum_{m=2}^n \gamma m = 1 + \gamma \frac{(n-1)(n+2)}{2}.$$ From here it is easy to deduce that $$T(n) = \Theta(n^2)$$.

I suggest now repeating your various methods, applying them directly to $$T_\gamma$$. Check which of them still works in this more concrete setting. Of course, if a method doesn't seem to work for $$T_\gamma$$, then in fact it didn't work already for the original recurrence $$T$$.

• Thank you for your detailed answer. When you say "otherwise, the following needs to be slightly modified", how would you modify it? That's because we are not really sure that $N=1$ so trying to be formal :) May 23, 2022 at 6:50
• You add more base cases, up to $n = N$. May 23, 2022 at 6:51
• Note that if $f(n)$ is positive for all natural $n \geq 1$ and $f(n) = \Theta(n)$, then there exist $0<c<C$ such that $cn \leq f(n) \leq Cn$ for all natural $n \geq 1$. That's a fact you can prove. May 23, 2022 at 6:52

Formaly, for all $$n>N$$,

$$T(n-1)+c_0n\le T(n)\le T(n-1)+c_1n$$

If we expand the right inequality, $$T(n)\le T(n-1)+c_1n\le T(n-2)+c_1n+c_1(n-1)\le\cdots \le T(N)+c_1\sum_{i={N+1}}^ni\\ =T(N)+c_1\frac{n^2+n-N^2-N}2.$$

We can repeat the reasoning with the left inequality. In the end, $$T(n)=\Theta(n^2-n-N^2-N)=\Theta(n^2)$$.