Given exam question:
Algorithms A & B have complexity functions $f(n)=10^6n+3n^2$ and $g(n)=1-2^{-20}n^3$ respectively.
[edit: It has been pointed out by Andre that the given complexity function $g(n)$ is meaningless -- therefore we infer a typo here and let $g(n)=1+2^{-20}n^3$ instead.]
By classifying each $f$ and $g$ as $\mathcal{O}(F)$ for a suitable function $F$, determine whether A or B is more efficient when $n$ is large.
Shouldn't the question ask for big-Theta instead of big-O? Consider the following answer:
We have $f(n) \in \mathcal{O}(n^2)$ and $g(n) \in \mathcal{O}(n^3)$. <--PremiseP
So when $n$ is large, $f(n) < g(n)$, thus algorithm A is more efficient. <--ConclusionP
But it's wrong to draw ConclusionP from PremiseP (just consider the counterexample $g(n)=n$).
On the other hand, the following answer is logical, but it doesn't quite answer the question:
We have $f(n) \in \Theta(n^2)$ and $g(n) \in \Theta(n^3)$.
So when $n$ is large, $f(n) < g(n)$, thus algorithm A is more efficient.
Was the given question correctly set, or is my reasoning correct?
Thanks!