1
$\begingroup$

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!

2 Answers 2

2

Yes, it should be $\Theta(.)$. For example, in the first answer you gave, $f$ is also $O(n^3)$, or $O(n^k)$ for $k\ge 2$. Alternatively you could show that $g$ is $\Omega(n^3)$ and that would work.

  • 0
    Ah yes, I see that alternatively, we could point out that $f(n)∈O(n2)$ and $g(n)∈Ω(n3)$ and hence deduce that A is more efficient than B. *[Assuming that the negative coefficient of $g(n)$ in the given question is indeed a typo and should be positive instead.]* BTW, thank you for addressing the crux of my question!2012-03-27
5

Note the minus sign in the formula for $g(n)$. Algorithm B is instantaneous, certainly $O(1)$. Implausibly, the bigger $n$ is, the less time algorithm B takes. For large $n$, it accomplishes the remarkable feat of taking a negative amount of time. Very useful if you have a slow computer! The question is a not very subtle trick question. Algorithm B is much more efficient than algorithm A, which is $\Theta(n^2)$.

  • 0
    Refer to http://math.stackexchange.com/a/124877/21813 re: the two conflicting definitions of big-O above.2012-03-27