patternMinor
Methods for Finding Asymptotic Lower Bounds
Viewed 0 times
lowerasymptoticmethodsforfindingbounds
Problem
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 $a0$ 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 uppe
$$\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 $a0$ 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 uppe
Solution
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.
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.
Context
StackExchange Computer Science Q#10511, answer score: 5
Revisions (0)
No revisions yet.