3
$\begingroup$

I've found in many exercises where I'm asked to show that $f(n)=\Theta(g(n))$ where the two functions are of the same order of magnitude I have difficulty finding a constant $c$ and a value $n_0$ for the lower bound. I'm using Corman's definition of $\Theta$:

$$\exists c_1,c_2>0\in\mathbb{R}:\forall n\geq n_0: 0 \leq c_1 g(n)\leq f(n)\leq c_2 g(n)$$

Showing the upper bound usually doesn't give me too much trouble, but for the lower bound I allot of times find myself using limits. And even though I'm getting the right answers, I'm a bit worried that my method isn't very rigorous and that maybe I'm doing a bit of hand waving in the process.

For example, problem 2.17 from Skiena's Algorithm Design Manual:

Show that for any $a,b\in \mathbb{R}: b>0$ that $(n+a)^b = \Theta(n^b)$

In this case I used limits to help find both constants.

For the upper limit I decided to look for some $c$ such that $(n+a)^b \leq c^bn^b$. So taking the $b$th root of each side and dividing by $n$ I have $\frac{n+a}{n}\leq c$ which gives me $1 + \frac{a}{n} \leq c$. For any $a\in\mathbb{R}$, $\lim_{n\to\infty }1+\frac{a}{n}=1$. If I pick $n_0>|a|$, then for $a<0$ the expression approaches 1 from the left starting arbitrarily close to $0$. If $a>0$ then the expression approaches 1 from the right starting arbitrarily close to 2. So choosing $c=2$ will satisfy the inequality and we have $c_2=2^b$.

Now for the lower bound. I'm looking at the same expression except with the inequality pointing the other way. In this case I'm trying to find $n_0$ and $c$ such that $c\leq 1+\frac{a}{n}$. The value of $n_0$ has to be greater than $|a|$ because otherwise we would have $c\leq 0$ which isn't allowed. This puts us in the same range of values between $0$ and $2$ approaching 1 from each side. So I choose any $c,n_0$ such that $n_0>|a|$ and $0 < c\leq 1-|\frac{a}{n_0}|$. So I could choose $n_0=3|a|$ and $c=\frac{2}{3}$.

Thus we have $0 < (\frac{2}{3})^bn^b \leq (n+a)^b \leq 2^bn^b$ for any $n \geq 3|a|$.

Is there an easier way to do this?

Normally when looking for upper limit constants where the two functions are of the same magnitude I simply eliminate negative lower order terms and change positive ones into multiples of the highest order term such as :

$$3n^2+15n-5\leq 3n^2+15n^2=18n^2$$

But when looking for the constant for the lower bound I find myself typically resorting to looking at limits. Is there any kind of short cut to finding the lower bound constant like there is for the upper bound constant?

$\endgroup$
  • $\begingroup$ Looks fine to me. $\endgroup$ – vonbrand Mar 13 '13 at 20:32
  • $\begingroup$ @vonbrand My question is if the use of limits to find the lower bound is really necessary, or is there some easier short-cut way of finding $c,n_0$ for the lower bound? $\endgroup$ – Robert S. Barnes Mar 14 '13 at 6:39
  • $\begingroup$ See also here. If you already have the function, finding lower bounds is boring. Imho. In particular, $(n+a)^b$ is a well-studied expression, cf binomial theorem. $\endgroup$ – Raphael Mar 14 '13 at 14:31
  • 1
    $\begingroup$ Rereading the question, what's wrong with the obvious: for a lower bound, drop positive terms. In your example, we have for large $n$: $3n^2 + 15n - 5 \geq 3n^2 + 14n \geq 3n^2$, which is obviously a tight lower bound on the leading coefficient. $\endgroup$ – Raphael Mar 15 '13 at 7:13
6
$\begingroup$

You can codify your method in the following lemma.

Lemma. If $f(n)/g(n) \rightarrow C$, where $C > 0$, then $f(n) = \Theta(g(n))$.

The proof is the same as the one you gave. After you prove this lemma once and for all, you can use it forever. That's actually a good way of verifying $f(n) = \Theta(g(n))$.

Note that the converse to the lemma isn't true. For example, let $f(n) = n$ and let $g(n) = \exp\lfloor\log n\rfloor$. The ratio $f(n)/g(n)$ moves inside the interval $[1,e)$, and in particular does not tend to a constant limit.

$\endgroup$
  • $\begingroup$ So you think this is a good general method and there's not really any easier short-cut way of finding the lower bound? $\endgroup$ – Robert S. Barnes Mar 14 '13 at 6:32
  • $\begingroup$ @RobertS.Barnes Depends on what quality of bound you want and what kind of algorithm you have at hand. $\endgroup$ – Raphael Mar 14 '13 at 14:30
2
$\begingroup$

Depending what $f$ and $g$ are precisely, you can use l'Hôpital's rule. The description from Wolfram Mathworld is quite good (the Wikipedia leaves out some cases leaving the definitions not quite correct).

In short (for the purposes of algorithmic analysis), if $\lim_{n\rightarrow\infty} f(n) = \lim_{n\rightarrow\infty} g(n) = 0$ or $\infty$, then: $$ \lim_{n\rightarrow\infty}\frac{f(n)}{g(n)} = \lim_{n\rightarrow\infty}\frac{f'(n)}{g'(n)} $$ (as long as $\lim_{n\rightarrow\infty}\frac{f'(n)}{g'(n)}$ exists)

So as long as you have fairly normal functions for your running time, and you remember some calculus, you can repeatedly apply this rule to determine whether $\lim_{n\rightarrow\infty}\frac{f(n)}{g(n)} = c$ for some constant $c$.

As a side note, the other cases still apply, so you can apply l'Hôpital's rule until you get one of three cases, the limit is $0$, $\infty$ or a constant, concluding that $f(n)\in O(g(n))$, $f(n)\in\Omega(g(n))$ or $f(n)\in\Theta(g(n))$ respectively.

The same caveat on the converse that Yuval mentions is of course still true here.

Raphael also gives some important limitations on using l'Hôpital with discrete functions (in that strictly you can't). See his comments here.

$\endgroup$
  • $\begingroup$ Indeed, that's what I've been doing. But my question was if there is any shortcut for finding an $n_0$ and constant $c$ for the lower bound like there is for the upper bound. $\endgroup$ – Robert S. Barnes Mar 14 '13 at 10:55
  • 1
    $\begingroup$ @RobertS.Barnes, ah, I was thinking of a shortcut to get the $\Theta$ result, rather than a shortcut to actually find the constant. However... I have a feeling (but not a proof on hand), that the limit value does give some information in this regard. I'll do some thinking and looking, or perhaps someone else can recall. A very hand wavy suggestion is that the $\lim\frac{f(n)}{g(n)}$ gives one, and $\lim\frac{g(n)}{f(n)}$ gives the other. Though it doesn't help immediately with the $n_{0}$. $\endgroup$ – Luke Mathieson Mar 14 '13 at 13:44
  • $\begingroup$ Regarding L'Hospital, please note my comments here; it's not a perfect match to our situation. $\endgroup$ – Raphael Mar 14 '13 at 14:31
  • $\begingroup$ @Raphael, good point, usually ignored. I'll link to it in the body. $\endgroup$ – Luke Mathieson Mar 15 '13 at 0:40

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.