Often in CLRS, when proving recurrences via substitution, $\Theta(f(n))$ is replaced with $cf(n)$.

For example, on page 91, the recurrence

$$ T(n) = 3T(⌊n/4⌋) + \Theta(n^2) $$

is written like so in the proof

$$ T(n) \le 3T(⌊n/4⌋) + cn^2. $$

But can't $\Theta(n^2)$ stand for, let's say, $cn^2 + n$? Would that not make such a proof invalid?

Further in the proof, the statement

\begin{align} T(n) &\le (3/16)dn^2 + cn^2 \\ &\le dn^2 \end{align}

is reached. But if $cn^2 + n$ was used instead of $cn^2$, that step would instead be the following

$$ T(n) \le (3/16)dn^2 + cn^2 + n $$

Can it still be proven that $T(n) \le dn^2$ if this is so? Do such lower order terms not matter in proving recurrences via substitution?


By definition, a function $f(n)$ is $\Theta(n^2)$ if there exist constant $b,c,N$ such that for all $n \geq N$, $$ bn^2 \leq f(n) \leq cn^2.$$ In particular, as long as $n \geq N$, we can always replace $f(n)$ by $cn^2$ when upper-bounding an expression.

In your example of $cn^2 + n$, when $n \geq 1$ we have $n \leq n^2$ and so $cn^2 \leq (c+1)n^2$.


Let me also suggest the following vision of the situation: $\Theta(f)$ is set of functions, which satisfy well know definition. So, when you wrote $T(n) = 3T(⌊n/4⌋) + \Theta(n^2)$, then this means $T(n) \in 3T(⌊n/4⌋) + \Theta(n^2)$, where right side is again set $g+\Theta(f) = \{g+\phi \colon \phi \in \Theta(f) \}$.

So, $T \in g+\Theta(f)$ mean that exists element of $g+\Theta(f)$ which is equal to $T$, but we cannot say, that $T$ equals to any member of $g+\Theta(f)$.

Same is if we write $$T(n)- 3T(⌊n/4⌋) \in \Theta(n^2)$$ Now, knowing the definition of belonging to a set, we just use it and write, that $\exists c_1, c_2 \gt 0, N\in \mathbb{N}$, such that for $n \gt N$ $$c_1 n^2 \leqslant T(n)- 3T(⌊n/4⌋) \leqslant c_1 n^2$$ saying exactly we do not "replace" $T(n)- 3T(⌊n/4⌋)$ in equality, but we "estimate" it in inequality.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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