Question 11 of 12

Question 11 (10 marks)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Given. (a) $f(n)=10\log(n!)$. (b)–(c) $T_A(n)=\Theta(n^2)$, $T_B(n)=\Theta(n\log n)$, fixed problem size $n=10$ in (b), general large $n$ in (c).

Find. (a) A proof $f(n)=O(n\log n)$ with an explicit witness constant. (b) Whether $A$ is certainly slower than $B$ at $n=10$, justified. (c) Whether an $n^*$ threshold beyond which $A$ is certainly slower exists, justified.

Approach. (a) bound $n!$ above by $n^n$ so $\log(n!)\le n\log n$; (b) exploit that $\Theta$ hides multiplicative constants and only bounds behavior for $n\ge n_0$, so a single fixed $n$ says nothing certain; (c) use the fact that $n^2/(n\log n)=n/\log n\to\infty$, which eventually beats any fixed hidden constant.

1. (a) $f(n)=10\log(n!)=O(n\log n)$. Since $n!=1\cdot2\cdots n\le n\cdot n\cdots n=n^n$ ($n$ factors, each $\le n$), taking logs (an increasing function) preserves the inequality: $$\log(n!)\ \le\ \log(n^n) = n\log n$$ Multiplying by 10: $$f(n)=10\log(n!) \le 10\,n\log n \quad\text{for all }n\ge1$$ This is exactly the $O(\cdot)$ definition with witness constant $C=10$ and threshold $n_0=1$ (or $n_0=2$ to keep $\log n>0$): $\boxed{f(n)=10\log(n!)=O(n\log n)\text{, witness }C=10}$
2. (b) Certain that A is slower than B at $n=10$? $\Theta$-notation only constrains behavior for $n\ge n_0$ for SOME unspecified threshold $n_0$, and hides unspecified positive constants: $T_A(n)=\Theta(n^2)$ really means $c_1 n^2\le T_A(n)\le c_2n^2$ for $n\ge n_0$, for some constants $c_1,c_2,n_0$ that are not given. At a small, fixed size like $n=10$, those hidden constants (and whether $n=10\ge n_0$ at all) can make $A$ faster than $B$ despite $A$'s worse asymptotic class. Concrete counterexample: let $T_A(n)=n^2$ and $T_B(n)=1000\,n\log_2 n$ (both valid representatives of their respective $\Theta$-classes). At $n=10$: $T_A=100$ but $T_B=1000\times10\times\log_2 10\approx33{,}219$ — here $A$ is drastically faster, not slower, than $B$. $\boxed{\text{NO}\text{ — }\Theta\text{ gives no certainty at one fixed small }n\text{; hidden constants can reverse the comparison}}$
3. (c) Does an $n^*$ threshold exist beyond which A is certainly slower than B? Unlike a single fixed point, the LIMIT of the ratio removes the constants' influence: for any positive constants $c_1$ (lower bound on $T_A$) and $c_2$ (upper bound on $T_B$), $$\dfrac{T_A(n)}{T_B(n)} \ \ge\ \dfrac{c_1 n^2}{c_2\, n\log n} = \dfrac{c_1}{c_2}\cdot\dfrac{n}{\log n}\ \xrightarrow[n\to\infty]{}\ \infty$$ since $n/\log n\to\infty$ regardless of the fixed ratio $c_1/c_2$. So no matter how the hidden constants are chosen, the ratio $T_A(n)/T_B(n)$ eventually exceeds 1 and stays above it, meaning $T_A(n)>T_B(n)$ for all sufficiently large $n$: $\boxed{\text{YES}\text{ — such an }n^*\text{ always exists, because }\Theta(n^2)\text{ asymptotically dominates }\Theta(n\log n)}$