1
$\begingroup$

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.

$\endgroup$
4
  • 2
    $\begingroup$ It’s not true that $\Theta(n-i)=\Theta(n)$. $\endgroup$ May 20, 2022 at 8:55
  • $\begingroup$ @YuvalFilmus, so sorry, $i$ is a constant, why ism't that an equivalence? I apologize if it is too trivial. $\endgroup$ May 20, 2022 at 9:34
  • 2
    $\begingroup$ But $i$ is not constant - it could be as large as $n-1$. $\endgroup$ May 20, 2022 at 9:35
  • 1
    $\begingroup$ 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$. $\endgroup$
    – rus9384
    May 21, 2022 at 15:36

2 Answers 2

2
$\begingroup$

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$.

$\endgroup$
3
  • $\begingroup$ 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 :) $\endgroup$ May 23, 2022 at 6:50
  • 1
    $\begingroup$ You add more base cases, up to $n = N$. $\endgroup$ May 23, 2022 at 6:51
  • 1
    $\begingroup$ 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. $\endgroup$ May 23, 2022 at 6:52
3
$\begingroup$

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)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.