Given exam question:
Algorithms A & B have complexity functions $f(n)=2 log(n^3)+3n$ and $g(n)=1+0.1n^2$ respectively.
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)$ and $g(n) \in \mathcal{O}(n^2)$. <--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)=1$).
On the other hand, the following answer is logical, but it doesn't quite answer the question:
We have $f(n) \in \Theta(n)$ and $g(n) \in \Theta(n^2)$.
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!