2
$\begingroup$

When we have only an asymptotic upper bound, we use $O$-notation. For a given function $g(n)$, we denote by $O(g(n))$ (pronounced “big-oh of $g$ of $n$” or sometimes just “oh of $g$ of $n$”) the set of functions

$$O(g(n))= \left\{ f(n):\text{ there exist positive constants }c\text{ and }n_0\text{ such that},\\ 0\leq f(n)\leq cg(n),\text{ for all }n\geq n_0 \right\}$$

This excerpt has been taken from introduction to algorithms 3rd edition. What I fail to understand is that how can algorithms with a linear runtime have an asymptotic upper bound when linear functions don't have asymptotes or is there a loophole in my thinking?

$\endgroup$
  • $\begingroup$ You are starting from a false premise. Linear functions do have asymptotes. I suspect that you are being misled by a misunderstanding of what asymptote means (modern meaning), possibly due to using the etymologic meaning of the word asymptote, which is not its current use. Although I linked to the wikipedia page for the modern meaning, be careful with that page. It is often edited and 'guarded' by people who add mistakes to it. $\endgroup$ – plop Sep 24 at 12:11
2
$\begingroup$

Word "asymptotic" is used to emphasize the condition $\exists n_0\in \mathbb{N}$ $\forall n> n_0$ for inequality $0\leqslant f(n) \leqslant C g(n)$ and generally does not contain any mention of limit or asymptotic. Even well known definition of O big, using $\lim\sup \frac{f}{g}$, have sense only when limit point for O big is not limit point for $g$'s zeros.

As to linear function, for example $f(n)=an+b$, then it easy to find solution for $an+b \leqslant C n $ finding $C>a$ and taking $ n \geqslant n_0= \lfloor \frac{b}{C-a} \rfloor+1 >0$. So we obtain $f(n)=an+b \in O(n)$ i.e. linear function is O-big $n$.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

The technical meaning of asymptotic upper bound is given by the definition of big O. That is, $g(n)$ is an asymptotic upper bound on $f(n)$ if $f(n) = O(g(n))$ according to the definition you wrote.

The term asymptote may have other meanings in other circumstances. For example, in analytic geometry, an asymptote of a function $f(x)$ is either a line $\ell(x)$ such that $\lim_{x\to\infty} [f(x)-\ell(x)] = 0$ (or the same with $x\to-\infty$), or a vertical line at a point $x_0$, i.e., $\lim_{x\to x_0-} f(x) = \infty$ (or $x_0+$, or $-\infty$).

The two definitions are different in several ways:

  • The geometric definition (per Wikipedia) uses $f(x) - \ell(x)$, whereas big O uses $f(x)/\ell(x)$.
  • The geometric definition asks $f(x)-\ell(x) \to 0$, whereas big O only asks that $f(x)/\ell(x)$ be bounded.
  • The geometric definition only allows $\ell(x)$ to be linear, whereas big O allows arbitrary functions (implicitly, eventually positive).
| cite | improve this answer | |
$\endgroup$

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.