0
$\begingroup$

Below is a problem worked out in the Introduction to Algorithms by Cormen et. al.

(I am not having problem with the proof but only I want to clarify the meaning conveyed by few statements in the text while solving the recurrence and the statements are given as ordered list at the end. Simply because I want to master the text.)

$$T(n) = 3T(\lfloor n/4 \rfloor) + \Theta(n^2)$$

Now the authors attempt to first find a good guess of the recurrence relation using the recursion tree method and for that they allow sloppiness and assumes $T(n)=3T(n/4) + cn^2$.

Recursion Tree

Though the above recursion tree is not quite required for my question but I felt like including it to make the background a bit clearer.

The guessed candidate is $T(n)=O(n^2)$. Then the authors proof the same using the substitution method.

In fact, if $O(n^2)$ is indeed an upper bound for the recurrence (as we shall verify in a moment), then it must be a tight bound. Why? The first recursive call contributes a cost of $\Theta(n^2)$ , and so $\Omega(n^2)$ must be a lower bound for the recurrence. Now we can use the substitution method to verify that our guess was correct, that is, $T(n)=O(n^2)$ is an upper bound for the recurrence $T(n) = 3T(\lfloor n/4 \rfloor) + cn^2$ We want to show that $T(n)\leq d n^2$ for some constant $d > 0$.

Now there are a few things which I want to get clarified...

(1) if $O(n^2)$ is indeed an upper bound for the recurrence. Here the sentence means (probably) $\exists$ a function $f(n) \in O(n^2)$ such that $T(n)\in O(f(n))$

(2) $\Omega(n^2)$ must be a lower bound for the recurrence Here the sentence means probably $\exists$ a function $f(n) \in \Omega(n^2)$ such that $T(n)\in \Omega(f(n))$

(3) $T(n)=O(n^2)$ is an upper bound for the recurrence $T(n) = 3T(\lfloor n/4 \rfloor) + cn^2$ This sentence can be interpreted as follows assume that $T'(n) = 3T'(\lfloor n/4 \rfloor) + cn^2$ and $\exists$ a function $T(n) \in O(n^2)$ such that $T'(n)\in O(T(n))$

(4) $T(n)\leq d n^2$ for some constant $d > 0$ We are using induction to verify to the definition of Big Oh...

I feel that the author could simply have written the $T(n)$ is Upper Bounded by $n^2$ and Lower Bounded by $n^2$ or the author could have simply written $T(n) = O(n^2)$ and $T(n)=\Omega(n^2)$, did the author just use the above style of statements as pointed out in $(1),(2),(3)$ just for more clearer explanation or there are some extra meaning conveyed which I am missing out.

$\endgroup$

1 Answer 1

1
$\begingroup$
  1. "$O(n^2)$ is indeed an upper bound for the recurrence" means $T(n) \in O(n^2)$. That is, $\exists n_0 \ge 1, c>0, \forall n \ge n_0, T(n) \le c n^2$.

  2. "$\Omega(n^2)$ must be a lower bound for the recurrence" means $T(n) \in \Omega(n^2)$. That is $\exists n_0 \ge 1, c>0, \forall n \ge n_0, T(n) \ge c n^2$.

  3. This is exactly the same as 1).

  4. Yes. In this step you use induction to show that $T(n) \le d n^2$ for some choice of a constant $d > 0$.

$\endgroup$
1
  • 1
    $\begingroup$ I was a bit confused with exact meaning as to whether they are using the asymptotic notation in the usual set sense as $O(n^2)$ is a set after all, or as an anonymous function. Thanks for the help. The statement is quite odd to interpret as the first meant a "set is an upper bound bound for the recurrence" and the second interpretation (as a function) as I thought which ultimately leads to what you said if we use the transitivity property for the Big Oh or Big Omega... $\endgroup$ Commented Jun 19, 2020 at 18:16

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.