In this lesson we will introduce our first asymptotic notation: the Big Oh, which can be used for expressing an upper bound for an algorithm's running time.
In the previous lesson The need for asymptotic notation: a case study we proved theoretically that for sufficiently large $n$, the running time of the second algorithm satisfies $T_2(n) < dn$ where $d$ is some constant. Here is the figure of measured running times again:
As said in the previous lesson, the figure confirms that we didn't make a mistake when calculating the theoretical upper bound: for example, from the figure one sees that $T_2(n) < 0.0021n$ if $n > 150$.
Why bother with theoretical analysis at all if one can measure running times in practice? Well, sometimes we want to have a rough estimate on the running time to decide whether to implement an algorithm at all; estimating worst-case running time (as opposed to average running time) based on measurements only is also not reliable (there could be some possible inputs taking a very long time but it might happen that we don't hit any of them in our benchmark). It can be quite hard to theoretically make claims with explicitly computed constants like “$T_2(n) < 0.0021n$ if $n > 150$”, but it is much easier to prove weaker statements like “for sufficiently large $n$, $T_2(n) < dn$ where $d$ is some constant”, which still give a rough idea. In computer science, such weaker statements are used so often that a shorter way for writing them has been invented: instead of “for sufficiently large $n$, $T_2(n) < dn$ where $d$ is some constant”, one writes
\[T_2 \in O(n).\]
This is what is called the Big Oh notation.
Before going to the general definition of Big Oh, let us note that in this and the following lessons, we will only talk about positive functions, i. e. functions whose values are positive real numbers. This is in order to simplify our definitions and properties of asymptotic notations a little. We will also assume that the function arguments are natural numbers. We will not demand the function to be defined and positive on all natural numbers, but only starting from some point (like $\log n$, which is defined and positive for $n \geq 2$). The function we are interested in will usually be the running time or memory consumption of an algorithm for given input size, which obviously satisfies these requirements (its value, i. e. running time or memory usage, is a positive real number, and the argument, i. e. the input size, is a natural number).
Definition (Big Oh).
Let $f$ and $g$ be two positive functions. We say that
$f$ grows asymptotically no faster than $g$ and write
$f\in O(g)$ if there exist constants $c\geq 0$ and $n_0$ such that for all $n \geq n_0$, we have that $f(n)\leq c\cdot g(n)$.
Figure (Big Oh). $f\in O(g)$ means that there exist some constants $c$ and $n_0$ such that for all $n \geq n_0$, $f(n) \leq cg(n)$.
We will sometimes also use the phrase sufficiently large: when saying “$P(n)$ for all sufficiently large $n$”, we mean “there exists $n_0$ such that $P(n)$ for all $n \geq n_0$”. So the definition of Big Oh can be rephrased like this: $f \in O(g)$ if and only if there exists a constant $c \geq 0$ such that $f(n) \leq c g(n)$ for all sufficiently large $n$.
The Big Oh notation has two characteristic properties:
it ignores the values of $f$ and $g$ for small $n$ and
it also ignores constant factors: if, e. g. a function $f$ is linearly bounded, i. e. $f(n) \leq dn$ for a constant $d$, then we can simply write $f \in O(n)$ without factor $d$.
If $f(n)$ is the running time of an algorithm for input size $n$, then this is usually indeed the most important information one needs about the algorithm's performance:
one really does not care how a running time behaves if it is sufficiently small;
multiplying the algorithm's running time by a moderate constant will not dramatically change the maximal input size for which the algorithm is usable — in contrast, replacing it with a more efficient algorithm can give an improvement of several orders of magnitude
1).
The Big Oh is the oldest in a family of mathematical notations, called asymptotic notations, which can be used to express how a function behaves when its argument grows to infinity. The Big Oh was taken into use by mathematician Paul Bachmann in the end of the 19th century, but is sometimes called the Landau symbol for another mathematician, Edmund Landau, who soon adopted it (the name Landau symbol is actually also used for a related asymptotic notation, the little oh; the latter was indeed introduced by Landau). For analyzing the performance of algorithms, the Big Oh has been popularized by the great computer scientist Donald Knuth, who also invented some other asymptotic notations (like the Big Omega, which we will meet later). Following Knuth, the Big Oh should actually be called the Big Omicron (a Greek letter that looks like the Latin O) — but most people still use Oh since this is easier to say and type.
Which of the following statements is true? (Justify your answer.)
$n \in O(2n+1)$
Solution True. Obvious (as the constant $c$ and $n_0$ in the definition of Big Oh we may take e. g. $c = 1$ and $n_0 = 0$). $2n+1 \in O(n)$
Solution True. Indeed, $2x+1 \leq 3x$ for all $x \geq 1$ (i. e., we can take $n_0 = 1$ and $c = 3$ in the definition of Big Oh).
$3n \in O(2n^2)$
Solution True. Note that for $x > 0$, the inequality $3x \leq 2x^2$ is equivalent to $1.5 \leq x$ (we divided both sides of the inequality by the positive number $2x$). So, $3n \leq 2n^2$ for all natural numbers $n \geq 2$, Q. E. D.2)
Geometrically, the graph of the function $y = 2x^2$ is an upwards-oriented parabola and the graph of $y = 3x$ is a line with positive slope. Actually, it is a rather intuitive geometrical fact that an upwards-oriented parabola through the origin always intersects twice a line with positive slope going through the origin, so that the second intersection point lies to the right of the origin and to the right of that point, the parabola lies higher than the line.
$2n^2 \in O(3n)$
Solution False. Let's suppose that $2n^2 \in O(3n)$ and show that this would give a contradiction. Indeed, $2n^2 \in O(3n)$ would mean that there exist $c$ and $n_0$ such that $2n^2 \leq 3cn$ for all $n \geq n_0$. Obviously then $c > 0$. Now take $m = \max \{2c,\ n_0\}$. Then $2m^2 \geq 4cm > 3cm$ (thanks to the inequalities $m \geq 2c$, $c > 0$ and $m > 0$), but at the same time $2m^2 \leq 3cm$ (since $m \geq n_0$) — a contradiction, Q. E. D. $2\in O(1)$.
Solution True. This statement should be interpreted as $f \in O(g)$ where $f$ and $g$ are the constant functions $f(n)=2$, $g(n)=1$. It is obviously true: as the constant $c$ and $n_0$ in the definition of Big Oh we may take $c = 2$ (or any larger number) and $n_0 = 0$ (or any other natural number). $\log_2 n\in O(n)$.
Solution True. Indeed, for all natural numbers $n > 0$, $\log_2 n \leq n$. To get this inequality, take the logarithm of the more obvious inequality $n \leq 2^n$. If the latter inequality is not obvious to you, use mathematical induction to convince yourself: $n \leq 2^n$ holds for $n = 0$, so we only have to prove that if it holds for some $n$, then it also holds for $n+1$. But that is easy to see: if we increase $n$ by $1$, then the left side of the inequality grows by $1$ but the right side doubles; since the right side is $\geq 1$, its doubling means it grows at least by $1$, so it must remain larger than the left side.
Given two functions $f$ and $g$, how to determine whether $f \in O(g)$ or not? We have already done it, using straightforwardly the definition of Big Oh, for some pairs of functions (we proved that $T_2 \in O(n)$ and some more such statements in the exercises), but actually there is a general approach which turns out very useful: this is to look at how their ratio $\frac{f(n)}{g(n)}$ behaves. Indeed, $f \in O(g)$ means that there exists some $c$ such that $f(n) \leq cg(n)$ for sufficiently large $n$; dividing this inequality by $g(n)$ (and recalling that we assume $g(n) > 0$), we get an equivalent inequality $\frac{f(n)}{g(n)} \leq c$. So we get the following criterion:
Criterion 1 (Big Oh means bounded ratio).. Let $f$ and $g$ be positive functions. We have $f \in O(g)$ if and only if the ratio $\frac{f(n)}{g(n)}$ is bounded for sufficiently large $n$ (i. e., there exists some constants $c$ and $n_0$ such that $\frac{f(n)}{g(n)} \leq c$ for all $n \geq n_0$).
For example, let's check whether $T_1(n) \in O(n^2)$ where $T_1(n)$ is the running time of our algorithm readNumbers1 in lesson The need for asymptotic notation: a case study. In that lesson, we got the formula
$T_1(n) = \frac{c}2n^2 + (d-\frac{c}2)n + e$
where $c$, $d$ and $e$ are some constants. The ratio is $\frac{T_1(n)}{n^2} = \frac{c}2 + (d-\frac{c}2)\frac1n + \frac{e}{n^2}$. Obviously we can make the last two terms as small as we like by choosing $n$ large enough. For example, there exist a number $n_0$ such that for all $n \geq n_0$, we have $(d-\frac{c}2)\frac1n < 0.1$ and $\frac{e}{n^2} < 0.1$. So $\frac{T_1(n)}{n^2} \leq \frac{c}2 + 0.2$ for sufficiently large $n$. Therefore, we have proven that $T_1 \in O(n^2)$. As the following diagram shows, measurements agree that ratio is indeed bounded: it appears that starting from $n \geq 50$ we have $\frac{T_1(n)}{n^2} < 2 \cdot 10^{-4}$.
Now let's check whether $T_1(n) \in O(n)$. The ratio is $\frac{T_1(n)}{n} = \frac{c}2 n + (d-\frac{c}2) + \frac{e}{n}$. The first term grows to infinity as $n \to \infty$, the second term is a constant and the third one goes to $0$ as $n \to \infty$, therefore the whole sum grows to infinity as $n \to \infty$. So the ratio $\frac{T_1(n)}{n}$ is not bounded in the process $n \to \infty$ (for any $c$ and $n_0$ there exists $n \geq n_0$ such that $\frac{T_1(n)}{n} > c$) and therefore we have proven that $T_1(n) \not\in O(n^2)$. The following diagram shows that measurements agree with the analysis: the ratio appears not to be bounded by any number but grow linearly to infinity.
Actually, often we can make our life even easier using the concept of limit. (To recall the definition and properties of the limit of a function, see page Limit.) Namely, if the limit $\lim_{n \to \infty} \frac{f(n)}{g(n)}$ exists then the ratio $\frac{f(n)}{g(n)}$ is bounded for sufficiently large $n$ if and only if the limit is finite; so, in order to determine whether $f \in O(g)$, it suffices to calculate the limit of the ratio of the functions. For example, let's recheck the statements $T_1 \in O(n^2)$ and $T_1 \in O(n)$. Since $\lim \frac{T_1(n)}{n^2} = \lim \frac{c}2 + \lim (d-\frac{c}2)\frac1n + \lim \frac{e}{n^2} = \frac{c}2 + 0 + 0 = \frac{c}2 < \infty$ but $\lim \frac{T_1(n)}{n} = \lim \frac{c}2 n + \lim (d-\frac{c}2) + \lim \frac{e}{n} = \infty + (d-\frac{c}2) + 0 = \infty$, we can immediately conclude that the first ratio is bounded for sufficiently large $n$ but the second one is not; hence $T_1 \in O(n^2)$ but $T_1 \not\in O(n)$. Looking at the $\frac{T_1(n)}{n^2}$ ratio diagram once more, we notice that measurements agree with the analysis that the ratio converges: from the diagram it looks like $\lim \frac{T_1(n)}{n^2} \approx 1.3 \cdot 10^{-4}$.
So we found the following general criterion for determining whether $f \in O(g)$.
Criterion 2 (Finite limit of ratio implies Big Oh).
Let $f$ and $g$ be positive functions. If $\lim_{n \to \infty} \frac{f(n)}{g(n)}$ exists, then $f \in O(g)$ if and only if $\lim_{n \to \infty} \frac{f(n)}{g(n)} < \infty$.
In some nasty cases, Criterion 2 cannot be applied since the limit does not exist. It turns out that an example is our function readNumbers2:
The diagram suggests that the ratio $\frac{T_2(n)}{n}$ does not converge to any particular number but keeps oscillating somewhere between 0.0021 and 0.0018; hence Criterion 2 cannot be used.3) Nevertheless, the ratio appears to be bounded for sufficiently large $n$ (the diagram suggests that $\frac{T_2(n)}{n} < 0.0021$ for $n > 150$) and this, by Criterion 1, means that $T_2 \in O(n)$. So this diagram agrees with our theoretical calculations in the first chapter that $T_2 \in O(n)$.
For most functions one encounters, however, the limit $\frac{f(n)}{g(n)}$ exists and Criterion 2 is useful.
Which of the following statements is true? (Justify your answer.)
$n^{23}\in O(n^{24})$.
Solution True. Indeed, $\lim_{n \to \infty} \frac{n^{23}}{n^{24}} = 0 < \infty$. Alternatively, this statement is also obvious from the definition of $Big Oh$, since for any $n \geq 1$, $n^{23} \leq n^{24}$. $n^{23}\in O(n^{22})$.
Solution False. Indeed, $\lim_{n \to \infty} \frac{n^{23}}{n^{22}} = \infty$. $n^{23}+n^3\in O(n^{23}+4)$.
Solution True. To calculate the limit of the ratio, we do a little trick: namely we divide both the nominator and the denumerator by $n^{23}$, finding that $\frac{n^{23}+n^3}{n^{23}+4} = \frac{\frac{n^{23}}{n^{23}}+\frac{n^3}{n^{23}}}{\frac{n^{23}}{n^{23}}+\frac4{n^{23}}} = \frac{1+\frac1{n^{20}}}{1+\frac4{n^{23}}}$. Since $\lim 1+\frac1{n^{20}} = \lim 1 + \lim \frac1{n^{20}} = 1 + 0 = 1$ and $\lim 1+\frac4{n^{23}} = 1$, we have $\lim \frac{n^{23}+n^3}{n^{23}+4} = \lim \frac{1+\frac1{n^{20}}}{1+\frac4{n^{23}}} = \frac{\lim 1+\frac1{n^{20}}}{\lim 1+\frac4{n^{23}}} = \frac{1}{1} = 1$. $12034273842374923+n^{23}+10+n^3\in O(12034273842374923)$. (The long number is the same on both sides.)
Solution False. Denoting $a = 1/12034273842374923$, we see that the ratio $\frac{12034273842374923+n^{23}+10+n^3}{12034273842374923} = an^{23} + an^3 + 10a + 1$ converges to infinity as $n \to \infty$. $n \in O(\log_2 n)$.
Solution False. It is a well known fact that $\lim_{x \to \infty} \frac{x^d}{(\log_a x)^b} = \infty$ for any constants $a > 0, b > 0, d > 0$. (This can be proven using L'Hospital's rule. You may also consult Wolfram Alpha for difficult limits, like this.) Therefore, $\lim_{n \to \infty} \frac{n}{\log_2 n} = \infty$. $n \in O(3^n)$.
Solution True. It is a well known fact that $\lim_{x \to \infty} \frac{x^d}{a^{x}} = 0$ for any constants $a > 0, d > 0$. (This can be proven using L'Hospital's rule. You may also consult Wolfram Alpha for difficult limits, like this.) Therefore, $\lim_{n \to \infty} \frac{n}{3^n} = 0 < \infty$. $3^n \in O(n)$.
Solution False. In the solution of the previous statement, we used the fact that $\lim_{n \to \infty} \frac{n}{3^n} = 0$. This implies that $\frac{3^n}{n} = \frac1{\frac{n}{3^n}}$ converges to $\infty$.
Lemma (Some properties of big Oh).
If $f\in O(g)$ and $a > 0$ then $a\cdot f\in O(g)$.
Proof
Suppose $f\in O(g)$. By the definition of Big Oh, this means that there exist numbers $c$ and $M$ such that for all $n \geq M$, we have $f(n) \leq c g(n)$.
We have to show that $a \cdot f\in O(g)$, i. e. that there exists some numbers $d$ and $N$ such that for all $n \geq N$, we have $a \cdot f(n) \leq d g(n)$. Obviously this is true if we take $N = M$ and $d = ac$, Q. E. D. The picture below illustrates the situation.
If $f_1\in O(g_1)$ and $f_2\in O(g_2)$ then $f_1+f_2\in O(g_1+g_2)$.
Proof
Suppose $f_1\in O(g_1)$ and $f_2\in O(g_2)$. By the definition of Big Oh, this means that there exist numbers $c_1$, $c_2$, $M_1$ and $M_2$ such that for all $n \geq M_1$, $f_1(n) \leq c_1 g_1(n)$ and for all $n \geq M_2$, $f_2(n) \leq c_2 g_2(n)$.
We have to show that there exist numbers $c_3$ and $M_3$ such that for all $n \geq M_3$, $f_1(n) + f_2(n) \leq c_3 (g_1(n) + g_2(n))$. We will show that one way to choose these two numbers is as follows: $c_3 := \max(c_1, c_2)$ and $M_3 := \max(M_1, M_2)$. Since $f_1(n) \leq c_1 g_1(n)$ for all $n \geq M_1$ and $c_3 \geq c_1$ and $M_3 \geq M_1$, the equality $f_1(n) \leq c_3 g_1(n)$ holds for all $n \geq M_3$. Analogously $f_2(n) \leq c_3 g_2(n)$ for all $n \geq M_3$. Adding these two inequalities, we have $f_1(n) + f_2(n) \leq c_3 g_1(n) + c_3 g_2(n)$ for all $n \geq M_3$.
Q. E. D.
If $f_1\in O(g_1)$ and $f_2\in O(g_2)$ then $f_1\cdot f_2\in O(g_1\cdot g_2)$.
If $f_1,f_2\in O(g)$ then $f_1+f_2\in O(g)$.
If $f_1 \in O(f_2)$ and $f_2\in O(g)$, then $f_1\in O(g)$.
If $g_1 \in O(g_2)$, then $g_1+g_2 \in O(g_2)$.
If $f\in O(g)$ and $\lim_{n \to \infty} b(n) = \infty$ then $\sum_{i=1}^{b(n)} f(i)\in O(\sum_{i=1}^{b(n)} g(i))$.
The following exercise demonstrates the power of asymptotic notation: using Big Oh estimates, one can get some idea about an algorithm's performance even if the exact expression for the running time is too difficult to calculate. (Of course, for some applications we might need the precise number of steps — in such cases, we cannot use asymptotic notation. But otherwise, asymptotics make life easier.)
Assume that you are analyzing the running time of an algorithm. Your analysis reveals:
The subroutine $f(a)$ does at most $a^2$ multiplications of integers of length $a$.
Besides that, $f(a)$ does some additional stuff. This additional stuff takes less time than $a$ multiplications, except if $a<a_0$ (due to some fixed overhead). $a_0$ is approximately $1000$, but you are not sure because computing the precise number would require much more work.
The main program calls $f(a)$ for each $a=1,\dots,n^3$ and performs at most $n^5$ additional elementary operations.
Multiplying integers of length $a$ takes time that is at most quadratic in $a$, up to some constant factor (i. e. at most $ka^2$ microseconds where $k$ is a constant).
Find a Big-Oh upper bound of the running time of the main program. More precisely, find a constant $d$ such that the program's running time is in $O(n^d)$; try to find the constant $d$ as small as possible. To justify your answer, use the properties stated in Lemma (Some properties of big Oh).
Hint. You may need the formula $\sum_{a=1}^{n^3} a^4=\frac{n^{15}}5+\frac{n^{12}}2+\frac{n^9}3-\frac{n^3}{30}$.
Solution
Answer. The running time of the program is in $O(n^{15})$.
Solution. The time needed for a multiplication of length-$a$ integers is $O(a^2)$ (since it is less than $ka^2$ where $k$ is a constant). The subroutine $f(a)$ does $a^2$ multiplications, so the total running time of those is in $O(a^4)$ (by property 3 in the Lemma). The “additional stuff” takes less than that, except for $a<a_0$. It is clear (from the definition of Big Oh) that the Big Oh notation ignores finitely many exceptions ($a=1,\dots,a_0-1$), so the additional stuff also takes time $O(a^4)$. Hence $f(a)$ takes time $O(a^4)$ (by property 3).
The main program calls $f(a)$ for $a=1,\dots,n^3$. The running time of these calls is then $O(\sum_{a=1}^{n^3} a^4)$ (by property 7). The hint says the sum can be expressed as a closed formula: $\sum_{a=1}^{n^3} a^4=\frac{n^{15}}5+\frac{n^{12}}2+\frac{n^9}3-\frac{n^3}{30}$. But if the sum is under Big Oh, it can be simplified further. The powers smaller than $n^{15}$ can be ignored, and the factor $\frac15$, too, so $\sum_{a=1}^{n^3} a^4 \in O(n^{15})$ (we used the obvious fact that $n^k \in O(n^{15})$ if $k \leq 15$ (since then $n^k \leq n^{15}$ for all natural numbers $n$) and properties 1 and 6 in the Lemma). Hence the calls of function $f$ take time $O(n^{15})$ in total (by property 5).
Finally, the main program runs $n^5$ elementary operations. This takes time $O(n^5)$ (no need to know the time for an elementary operation, as long as it is bounded by a constant). So the total running time is in $O(n^{15}+n^5)$. Since $n^5 \in O(n^{15})$, it is equivalent to say that the total running time is in $O(n^{15})$ (by property 5).
Remark. Let us note that an exact expression of the running time (instead of the asymptotic upper bound $O(n^{15})$) would be much more difficult to calculate. After some calculations, we would find the algorithm's running time to be at most $\sum_{a=0}^{a_0-1} \mathit{time}(f(a))+\sum_{a=a_0}^{n^3} 2ka^4 + n^5e$, where $e$ is an upper bound for the running time of an elementary operation. This is a rather complex summation formula with various parameters ($e$ and $m$) that depend on the specific machine and implementation details and with the annoying $\sum_{a=0}^{a_0-1} \mathit{time}(f(a))$ that is only relevant for small $a$'s anyway. Although such a detailed analysis may be required in some cases, in many cases we would be happy with an estimate that shows the essential complexity of the algorithm, without getting into too many details of the formula. This is possible using asymptotic notation.
Lemma (Big Oh relations of some well-known functions).
$p(n) \in O(n^k)$ if $p$ is a polynomial of degree $k$.
$n^k \in O(a^n)$ for any constant real numbers $a > 1$ and $k > 0$.
$(\log_a n)^k \in O(n^l)$ for any constant real numbers $a > 1$, $k > 0$ and $l > 0$.
$\log_a n \in O(\log_b n)$ for any constant real numbers $a > 1$ and $b > 1$.
$a^n \in O(b^n)$ for any constant real numbers $b \geq a > 0$.
