I was learning ϴ(n) notation in my course "Asymptotic Analysis for Algorithms" when I encountered the following example:

For any non-negative constants $c_1\geq 0,c_2\geq 0,n\geq n_0$ we have the following inequality:

$$c_1\leq\frac{1}{2}-\frac{3}{n}\leq c_2$$

For these constants to satisfy this inequality, will be $c_2\geq\frac{1}{2}$ when $n\geq 1$. This is the part I'm having issues with.

I tried to derive it assuming $n \geq 1$ and I found:

\begin{align*} c_2 &\geq \frac{1}{2} - \frac{3}{n} \\ \implies c_2 &\geq \frac{1}{2} - \frac{3}{1} \\ \implies c_2 &\geq -\frac{5}{2}` \end{align*}

I managed to show the left inequality holds when $n\geq 7$ and $c_1\leq \frac{1}{14}$.

  • 1
    $\begingroup$ $3/n$ is positive, so $1/2-3/n$ will be smaller than $1/2$. In other words, $1/2-3/n \leq 1/2$. Thus you can choose $c_2$ to be anything bigger than this upper bound of $1/2$ if you want it to be an upper bound too. So $1/2-3/n \leq c_2$ if $c_2 \geq 1/2$. $\endgroup$ – Antonio Vargas Nov 2 '16 at 7:49

The point is $-3/n$ is increasing to zero, so for large $n$ $1/2-3/n$ is approximately (but less than) $1/2$

In other words $1/2-3/n \ge 1/2-3/1$ is wrong, so you cannot derive the second inequality from the first one.


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.