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(x)=3x^7+x^5\log x^9+\dfrac1x$. (b) $T_A(n)=\Theta(n^{10})$, $T_B(n)=\Theta(10^n)$.

Find. (a) An $\Omega(x^7)$ proof (witness constants $C,k$). (b) The truth value of each of the three statements, with justification.

Approach. (a) bound $f(x)$ below by a constant multiple of $x^7$ for $x$ large enough. (b) recall that Big-$\Theta$ fixes a runtime's growth only up to unknown constant factors and only for large $n$, so statements about one specific $n$ need care; compare the two functions' actual growth rates using ratios and limits.

1. (a) Show $f(x)=3x^7+x^5\log x^9+\dfrac1x$ is $\Omega(x^7)$. We need constants $C\gt0$ and $k$ with $f(x)\ge C\,x^7$ for all $x\ge k$. For $x\ge1$: $\log x^9=9\log x\ge0$, so $x^5\log x^9\ge0$; and $\dfrac1x\gt0$. Dropping these two non-negative terms can only decrease $f$: $$f(x)=3x^7+9x^5\log x+\frac1x\ \ge\ 3x^7\quad\text{for all }x\ge1$$ This is the definition of $\Omega(x^7)$ with witnesses $C=3$, $k=1$ (any logarithm base greater than 1 works, since only $\log x\ge0$ for $x\ge1$ is used). In fact $f(x)/x^7\to3$, so $f$ is also $O(x^7)$ and hence $\Theta(x^7)$, but only the lower bound is asked. $$\boxed{f(x)=\Omega(x^7)\ \text{with witnesses } C=3,\ k=1}$$
2. (b)(i) Is it CERTAIN that B is slower than A at $n=20$? $\Theta$ fixes each runtime only up to unknown constant factors and only beyond some threshold: $T_A(n)\approx c_A n^{10}$ and $T_B(n)\approx c_B 10^n$ with $c_A,c_B$ unknown. Even though the bare growth functions give $10^{20}\gt 20^{10}\approx1.02\times10^{13}$, a large enough $c_A$ (or a threshold beyond $n=20$) could make A the slower one at this single size, so nothing is certain about one specific $n$. $$\boxed{\text{FALSE} \text{ — asymptotic notation gives no certainty about a single specific } n}$$
3. (b)(ii) Is the expected slowdown factor from $n$ to $2n$ equal to $n^{10}$? With $T_A(n)\approx c\,n^{10}$ for large $n$ (the unknown constant $c$ cancels), the ratio between problem sizes $2n$ and $n$ is: $$\frac{T_A(2n)}{T_A(n)}=\frac{(2n)^{10}}{n^{10}}=2^{10}=1024$$ This ratio is the CONSTANT $2^{10}=1024$, independent of $n$ — not $n^{10}$ (which would grow without bound as $n$ increases). The statement confuses the absolute growth rate ($n^{10}$) with the doubling-ratio (a fixed constant for a polynomial of fixed degree). $$\boxed{\text{FALSE} \text{ — the correct factor is } 2^{10}=1024\text{, a constant, not } n^{10}}$$
4. (b)(iii) Does B eventually and permanently take longer? Because the bounds are $\Theta$ (tight), there are constants with $T_B(n)\ge c_1 10^n$ and $T_A(n)\le c_2 n^{10}$ for all large $n$. The ratio $\dfrac{c_1 10^n}{c_2 n^{10}}\to\infty$ as $n\to\infty$ (an exponential with base greater than 1 dominates every fixed-degree polynomial), so it exceeds 1 beyond some $n^*$ and stays above 1 for every larger $n$. For the bare functions: $n^{10}\gt10^n$ for $2\le n\le9$, the two tie at $n=10$, and $10^n\gt n^{10}$ for every $n\ge11$. $$\boxed{\text{TRUE} \text{ — exponential growth eventually and permanently dominates any fixed-degree polynomial}}$$