Exercises — Big-O notation — formal definition, mathematical

(b). We need one multiplier $c$ and one threshold $n_0\in \mathbb{N}$, after which the one-sided bound holds forever. Option (a) quantifies $n_0$ wrongly (it demands the bound at every threshold, meaningless). Option (c) with "$\forall c$" is actually the definition of little-o (Little-o and little-omega), a strictly stronger statement — don't confuse them.

True. Take $c=7,n_0=0$: $7n\le 7\cdot n$ trivially. Constant factors vanish — that is the whole point of Big-O.

True, but loose. For $n\ge 1$: $n\le n^2$, so $c=1,n_0=1$. Big-O is only an upper bound, so a function may be $O$ of something that grows strictly faster. It is not tight — a tight statement would need $\Theta$, and $n\ne \Theta (n^2)$.

Goal: find $c,n_0$ with $6n+4\le cn$ for $n\ge n_0$. Step (bound the small term by the big one): for $n\ge 4$ we have $4\le n$, so $6n+4\le 6n+n=7n(n\ge 4).$ Read off: $c=7,n_0=4$. $■$ (Any valid pair works, e.g. $c=10,n_0=1$ since $6+4=10\le 10$. You only need one.)

Push every lower power up to $n^2$. For $n\ge 1$: $2n\le 2n^2$ and $9\le 9n^2$. Hence $4n^2+2n+9\le 4n^2+2n^2+9n^2=15n^2(n\ge 1).$ Read off: $c=15,n_0=1$. $■$ This is the polynomial rule: a degree-$d$ polynomial is $O(n^d)$.

Since ${\log }_{2}n\le n$ for every $n\ge 1$ (a log grows slower than its argument), take $c=1,n_0=1$: $0\le {\log }_{2}n\le 1\cdot n(n\ge 1).■$ Look at the s01 figure: ${\log }_{2}n$ (green) stays flat under the linear line — this is why any log is $O(n)$.

True. For $n\ge 1$: $n\le n^2$, so $n^2+n\le n^2+n^2=2n^2(n\ge 1),$ giving $c=2,n_0=1$. $■$

False. Suppose $n^3\le c{n}^2$ for all $n\ge n_0$. Since $g(n)=n^2>0$ for $n\ge 1$, we may divide by $n^2$: $n\le c\text{for all }n\ge \max (n_0,1).$ But $c$ is a fixed constant while $n$ grows without bound — contradiction once $n>\max (c,n_0,1)$. No pair $(c,n_0)$ exists. $■$ The breaking technique: isolate a term that grows and show it must exceed the fixed $c$.

True. Rewrite: $2^{n+1}=2\cdot 2^n$. So $2^{n+1}\le 2\cdot 2^n(\text{all }n\ge 0),$ giving $c=2,n_0=0$. $■$ Key insight: a constant shift in the exponent is just a constant multiplier, which $c$ absorbs. (Contrast: $2^{2n}=4^n$ is not $O(2^n)$ — see L5.)

By hypothesis there exist constants:

• $c_1,m_1$ with $f_1(n)\le c_{1}n$ for $n\ge m_1$;
• $c_2,m_2$ with $f_2(n)\le c_2{n}^2$ for $n\ge m_2$.

Set $n_0=\max (m_1,m_2,1)$. The reason $1$ appears in this max: the step $n\le n^2$ is only true for $n\ge 1$ (for $0<n<1$ it would fail, and $n=0$ gives equality), so we must force $n\ge 1$ before using it. For $n\ge n_0$ all three facts hold at once — $f_1\le c_{1}n$, $f_2\le c_2{n}^2$, and $n\le n^2$ — hence $f_1(n)+f_2(n)\le c_{1}n+c_2{n}^2\le c_1{n}^2+c_2{n}^2=(c_1+c_2)n^2.$ Read off: $c=c_1+c_2,n_0=\max (m_1,m_2,1)$. $■$ This is the sum rule: $O(f)+O(g)=O(\max (f,g))$, the dominant term wins.

There exist $c_1,m_1$ with $f(n)\le c_{1}n$ ($n\ge m_1$) and $c_2,m_2$ with $g(n)\le c_2{\log }_{2}n$ ($n\ge m_2$). Since both $f,g\ge 0$, for $n\ge n_0=\max (m_1,m_2)$: $f(n)g(n)\le (c_{1}n)(c_2{\log }_{2}n)=(c_1{c}_2)\left(n{\log }_{2}n\right).$ Read off: $c=c_1{c}_2,n_0=\max (m_1,m_2)$. $■$ This is exactly why merge sort's $n$ merges each costing ${\log }_{2}n$ levels give $O(n{\log }_{2}n)$.

Step 1 — chain two known facts. From the parent note, $3n+7=O(n)$: there are $c_1=4,m_1=7$ with $3n+7\le 4n(n\ge 7).$ From L1.3, $n=O(n^2)$: there are $c_2=1,m_2=1$ with $n\le 1\cdot n^2(n\ge 1).$ Step 2 — unify the thresholds. Both bounds must hold simultaneously, so take $n_0=\max (m_1,m_2)=\max (7,1)=7.$ Step 3 — multiply the constants along the chain. For every $n\ge n_0=7$: $3n+7\le c_{1}n=4n\le c_1(c_2{n}^2)=4\cdot 1\cdot n^2=4n^2.$ Read off: $c=c_1{c}_2=4,n_0=7$. $■$ This is transitivity made concrete: $f=O(g)$ and $g=O(h)$ give $f=O(h)$ with constant $c_1{c}_2$ and threshold $\max (m_1,m_2)$.

False. Rewrite $2^{2n}=(2^2{)}^n=4^n$. Suppose $4^n\le c{2}^n$ for $n\ge n_0$. Divide by $2^n>0$: $2^n\le c\text{for all }n\ge n_0.$ But $2^n\to \infty$ while $c$ is fixed — contradiction once $2^n>c$, i.e. $n>{\log }_{2}c$. No pair exists. $■$ Compare with L3.3: additive shifts in the exponent are safe; multiplying the exponent (changing the base) is not.

True. Since $\sin n\le 1$ for all $n$, we have $1+\sin n\le 2$, hence $f(n)=n(1+\sin n)\le 2n(\text{all }n\ge 0).$ So $c=2,n_0=0$. $■$ Big-O does not require $f$ to be monotone or smooth — only that it stays under $cg$ eventually. Oscillation between $0$ and $2n$ is completely fine. (Note: $f$ is not $\Omega (n)$, since it dips to $0$ infinitely often, so it's not $\Theta (n)$.)

$f=0$ is $O(g)$ for every nonnegative $g$: $0\le 0\le cg(n)$ holds for any $c>0$ and $n_0=0$. The zero function is the "smallest" thing — it's $O$ of everything. If $g(n)=0$ too: then $f=O(g)$ requires $0\le f(n)\le c\cdot 0=0$, forcing $f(n)=0$. So $0=O(0)$ is fine, but a positive $f$ is never $O(0)$. $■$ This is the limiting/degenerate boundary of the definition — the bound $cg$ collapses to $0$. It is exactly the case our standing assumption ($g>0$ on its tail) excludes, so we handle it by hand here.

Form the ratio $f/g$ with $f=\frac{n^2}{{\log }_{2}n}$, $g=n$: $\frac{f(n)}{g(n)}=\frac{n^2}{n{\log }_{2}n}=\frac{n}{{\log }_{2}n}.$ As $n\to \infty$, $\frac{n}{{\log }_{2}n}\to \infty$ (the numerator outgrows the slow log). If $f=O(g)$ then $f/g\le c$ would have to hold past some $n_0$ — but the ratio is unbounded. So $\frac{n^2}{{\log }_{2}n}\ne O(n)$. $■$ Why the limit tool? When picking $c,n_0$ by hand is awkward, ${\lim }_{n\to \infty }f/g$ answers "does the ratio stay bounded?" directly: a finite limit (or bounded ratio) $\Rightarrow f=O(g)$; an infinite limit $\Rightarrow$ not $O$.

L1 — read the definition, spot direction (upper bound, not symmetric). L1 recall ::: L1.1 is (b); L1.2 true; L1.3 true but loose. L2 — produce $(c,n_0)$; push lower terms to the top power. L2 recall ::: $6n+4$: $c=7,n_0=4$. $4n^2+2n+9$: $c=15,n_0=1$. ${\log }_{2}n$: $c=1,n_0=1$. L3 — decide + disprove via $n\to \infty$; exponent shifts. L3 recall ::: $n^2+n=O(n^2)$ true ($c=2$); $n^3\ne O(n^2)$; $2^{n+1}=O(2^n)$ ($c=2$). L4 — combine rules with unified thresholds. L4 recall ::: sum $\Rightarrow O(n^2)$; product $\Rightarrow O(n\log n)$; transitivity $\Rightarrow O(n^2)$ with $c=4,n_0=7$. L5 — degenerate/oscillating/limit cases. L5 recall ::: $2^{2n}\ne O(2^n)$; $n(1+\sin n)=O(n)$; $0=O(g)$ always; $\frac{n^2}{\log n}\ne O(n)$.