Exercises — Tight bounds — Θ notation; lower bounds — Ω notation

WHAT: we compare $7n+100$ against $g(n)=n$. WHY $\Theta$: the leading term is $7n$, which grows exactly like $n$; the $+100$ is a constant that $n_0$ washes out. Since $n$ is both a floor and a ceiling (with $c_1=7$, $c_2=8$, $n_0=100$: for $n\ge 100$, $100\le n$ so $7n+100\le 8n$), the tight symbol applies. Picture: in the sandwich figure this is the case where $f$ (here $7n+100$) slots between $7n$ and $8n$ past $n_0=100$. Answer: $7n+100=\Theta (n)$.

True. $O$ is only a ceiling. Since $n\le 1\cdot n^2$ for all $n\ge 1$, $n$ sits under $n^2$, so $n=O(n^2)$ — even though $n^2$ is a loose ceiling here. This is exactly the "$O$ can be loose" point from the parent: a smaller-order function is always $O$ of a larger one. Picture: only the yellow ceiling of the sandbox figure is used; there is no matching green floor of shape $n^2$ under $n$.

$\Theta$. Change-of-base gives ${\log }_{2}n=\frac{{\log }_{10}n}{{\log }_{10}2}$, a constant multiple of ${\log }_{10}n$. A constant factor is exactly what $c_1,c_2$ absorb, so the bases don't matter: ${\log }_{2}n=\Theta ({\log }_{10}n)$. This is why we often write $\log n$ with no base in complexity.

WHAT: we bound above by a scaled $n^2$. WHY the step: replace the smaller-order term $3n$ by something $\le$ a copy of $n^2$, because making the right side bigger keeps the "$\le$" valid. For $n\ge 1$, $3n\le 3n^2$. So $4n^2+3n\le 4n^2+3n^2=7n^2.$ Picture: $7n^2$ is the yellow ceiling of the sandwich figure for this $f$. Answer: $c=7$, $n_0=1$. Hence $4n^2+3n=O(n^2)$. ∎

WHAT: we need a floor $c_1{n}^2\le f(n)$. WHY the step: drop the positive term $3n$ — throwing away a positive quantity only shrinks the expression, which is exactly the direction a floor needs. For $n\ge 1$, $4n^2+3n\ge 4n^2.$ So $c_1=4$, $n_0=1$ gives $\Omega (n^2)$. (We pick $n_0=1$ rather than $0$ to keep the whole page on the same domain $n\ge 1$ — the same domain where dividing by $n$ is safe.) Picture: $4n^2$ is the green floor of the sandwich figure. Conclude $\Theta$: combining L2-a and this, $4n^2\le f(n)\le 7n^2$ for $n\ge 1$, so $f=\Theta (n^2)$ with $c_1=4,c_2=7,n_0=1$ — the full sandwich is now built. ∎

WHY the limit test: the parent's shortcut says a finite nonzero ratio means "same shape." Compute $L={\lim }_{n\to \infty }\frac{6n^3}{n^3}=6.$ Since $0<6<\infty$, we land in the $\Theta$ case. Answer: $6n^3=\Theta (n^3)$. The value $L=6$ is literally a legal $c$ between the sandwich constants — in the figure, any $c_1<6<c_2$ traps $f$.

WHAT: show no constant $c$ makes $n^2\le cn$ hold for all large $n$. WHY by contradiction: suppose such $c$ exists. Divide both sides by $n>0$ (legal for positive $n$): $n\le c.$ The picture: this demands the ever-growing quantity $n$ stay under a fixed number $c$ forever — impossible, since $n$ eventually passes any fixed $c$ (take $n=\lceil c\rceil +1$, which is $>c$). No ceiling of shape $n$ can hold $n^2$ down: in the sandwich figure the yellow line $c\cdot n$ would be crossed by $f=n^2$. Contradiction. Answer: $n^2\ne O(n)$; hence $n^2=\Omega (n)$ but not $\Theta (n)$. ∎

No. A single $\Theta (g)$ would need one $g$ sandwiching $T(n)$ for every input of size $n$. But $T$ ranges from order $n$ (sorted input) to order $n^2$ (reverse input) — two different orders. No single power can be both floor and ceiling across that spread. Correct statement: overall $T(n)=O(n^2)$ and $T(n)=\Omega (n)$; the tight $\Theta$ exists only per case. See Best, worst, and average case analysis.

WHY the limit: it separates strict orders. $L={\lim }_{n\to \infty }\frac{n{\log }_{2}n}{n}={\lim }_{n\to \infty }{\log }_{2}n=\infty .$ $L=\infty$ ⇒ $f=\Omega (g)$ but not $O(g)$: $n\log n$ is strictly larger order than $n$. Using the definition from the top of this page, that "strictly larger, not tight" situation is exactly $f=\omega (n)$ (little-omega). Answer: $n{\log }_{2}n=\Omega (n)$, not $\Theta (n)$.

WHY the Master Theorem: it hands a $\Theta$ directly for divide-and-conquer recurrences $T(n)=aT(n/b)+f(n)$. Here $a=2$, $b=2$, $f(n)=n$. Compare $f(n)=n$ with $n^{{\log }_{b}a}=n^{{\log }_{2}2}=n^1=n$. They match ⇒ the "balanced" case ⇒ multiply by a $\log$: $T(n)=\Theta (n\log n).$ Sanity check: this is exactly merge sort's recurrence, and merge sort is $\Theta (n\log n)$. ✓

WHAT: bound the sum both ways. The closed form is $S(n)=\frac{n(n+1)}{2}=\frac{n^2+n}{2}$. Ceiling: $\frac{n^2+n}{2}\le \frac{n^2+n^2}{2}=n^2$ for $n\ge 1$, so $c_2=1$ (yellow line of the sandwich). Floor: $\frac{n^2+n}{2}\ge \frac{n^2}{2}$ (drop the positive $n$), so $c_1=\frac{1}{2}$ (green line). Answer: $\frac{1}{2}{n}^2\le S(n)\le n^2$ for $n\ge 1$ ⇒ $S(n)=\Theta (n^2)$. ∎

WHY: in a sum of two nonnegative growths, the larger order dominates — the smaller one is eventually a lower-order term absorbed by the sandwich constants. Formally $f+h\le c_2{n}^2+d_{2}n\le (c_2+d_2)n^2$ (ceiling) and $f+h\ge c_1{n}^2$ (floor, since $h\ge 0$). Answer: $f(n)+h(n)=\Theta (n^2)$.

The two bounds live on different objects:

• $\Omega (n\log n)$ is a bound on the problem — every possible comparison-based algorithm must make at least this many comparisons in the worst case. It comes from the decision tree: a tree with $n!$ leaves (one per possible ordering) has height $\ge {\log }_2(n!)$, and ${\log }_2(n!)=\Theta (n\log n)$.
• $O(n\log n)$ is a bound on one algorithm (merge sort's worst-case cost). Why optimal: the algorithm's ceiling meets the problem's floor at the same order. No algorithm can beat $\Omega (n\log n)$, and merge sort reaches it, so merge sort is worst-case $\Theta (n\log n)$ and cannot be asymptotically improved. ∎

Ceiling: each of the $n$ factors is $\le n$, so $n!\le n^n$, giving ${\log }_2(n!)\le n{\log }_{2}n$. So $c_2=1$. Floor: keep only the top half of the factors — the $n/2$ integers from $n/2$ up to $n$ are each $\ge n/2$: $n!\ge (\frac{n}{2}{)}^{n/2}\Rightarrow {\log }_2(n!)\ge \frac{n}{2}{\log }_2\frac{n}{2}=\frac{n}{2}({\log }_{2}n-1).$ The justification step: we want ${\log }_{2}n-1\ge \frac{1}{2}{\log }_{2}n$. Rearranging, this is $\frac{1}{2}{\log }_{2}n\ge 1$, i.e. ${\log }_{2}n\ge 2$, i.e. $n\ge 4$. So precisely because $n\ge 4$ forces ${\log }_{2}n\ge 2$, the inequality holds. Therefore for $n\ge 4$, ${\log }_2(n!)\ge \frac{n}{2}\cdot \frac{1}{2}{\log }_{2}n=\frac{n}{4}{\log }_{2}n,$ i.e. $c_1=\frac{1}{4}$. Answer: $\frac{1}{4}n{\log }_{2}n\le {\log }_2(n!)\le n{\log }_{2}n$ for $n\ge 4$ ⇒ $\Theta (n\log n)$. ∎

First pair: $\frac{2^{n+1}}{2^n}=2$, a constant. $L=2\in (0,\infty )$ ⇒ yes, $2^n=\Theta (2^{n+1})$: multiplying an exponent's argument shift by a constant just rescales — a constant factor the sandwich absorbs. Contrast: $\frac{3^n}{2^n}=(3/2{)}^n\to \infty$. Here the base differs, so $L=\infty$: $3^n=\omega (2^n)$ (little-omega — strictly larger order, as defined at the top), not $\Theta$. Moral: constant multipliers keep the class; different bases change it. See Asymptotic comparison of functions.

L1 recognise the symbol → L2 exhibit $c,n_0$ → L3 find where a bound fails → L4 combine tools (Master Theorem, sums) → L5 reason about problems and prove optimality.