Question 11 of 12

Question 11

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. $T_A(n)=\Theta(n^3)$, $T_B(n)=\Theta(4^n)$; $f(n)=5n+3\log(n!)$.

Find. (a) whether $T_B(4)>T_A(4)$ can be concluded. (b) whether $T_A(2k)/T_A(k)\approx8$ for large $k$. (c) a Big-O proof for $f(n)$.

Approach. $T(n)=\Theta(g(n))$ means there are constants $c_1,c_2>0$ and $n_0$ with $c_1g(n)\le T(n)\le c_2g(n)$ for all $n\ge n_0$: it fixes the growth rate, not the constants, and says nothing below $n_0$. Apply that to a single small $n$ in (a) and to a ratio at large $n$ in (b); in (c) bound $\log(n!)$ by $n\log n$.

1. a) Is B slower than A at $n=4$? $\boxed{\text{No, it cannot be concluded.}}$ The bare functions give $4^4=256$ versus $4^3=64$, but $\Theta$ hides unknown constant factors and lower-order terms, and it only constrains behaviour for $n\ge n_0$, where $n_0$ is unknown and may exceed 4. For example, $T_A(n)=1000n^3$ and $T_B(n)=4^n$ are valid $\Theta(n^3)$ and $\Theta(4^n)$ running times with $T_A(4)=64{,}000>T_B(4)=256$. Asymptotic notation only guarantees that B is eventually (for large enough $n$) slower.
2. b) Is $T_A(2k)\approx8\,T_A(k)$ for large $k$? If the running time behaves like its leading term, $T_A(n)\approx c\,n^3$ for large $n$, then $$\frac{T_A(2k)}{T_A(k)}\approx\frac{c(2k)^3}{c\,k^3}=2^3=8,$$ and the unknown constant $c$ cancels because it is the same algorithm at both sizes. So $\boxed{\text{Yes, approximately }8\times}$ under the usual reading that $T_A(n)/n^3$ tends to a constant. Strictly, $\Theta(n^3)$ alone only bounds the ratio between $8c_1/c_2$ and $8c_2/c_1$, so "approximately eight" is justified by the leading-term behaviour of a cubic-cost algorithm, not by the $\Theta$ symbol by itself.
3. c) Show $f(n)=5n+3\log(n!)$ is $O(n\log n)$. $\log(n!)=\log1+\log2+\cdots+\log n\le n\log n$ (each of the $n$ terms is at most $\log n$). For $n\ge2$ (base-2 logs, so $\log n\ge1$ and $n\le n\log n$): $$f(n)=5n+3\log(n!)\le5n\log n+3n\log n=8n\log n.$$ With witnesses $c=8$, $n_0=2$: $\boxed{f(n)=O(n\log n)}$. (For another log base $b$, the same argument works from $n_0=b$, or with a larger constant, since logs of different bases differ by a constant factor.)