# Why do algorithms with runtime of O(n) are said to have asymptotic upper bound, when linear functions don't have asymptotes?

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?

• 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.
– plop
Sep 24 '20 at 12:11

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$$.

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).