# Abuse of big-O notation?

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.

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!

-

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.

-
How is $g = o(n^3)$? – Antonio Vargas Mar 26 '12 at 22:20
Oops, you're right. I meant $\Omega(n^3)$, that $n^3$ is a lower bound for $g$. – Patrick Mar 26 '12 at 22:37
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! – Ryan Mar 27 '12 at 14:11

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)$.

-
I really want to see that Algorithm B in operation when $n>101$. – Brian M. Scott Mar 26 '12 at 21:30
Oh, thanks for pointing out the negative coefficient of $n^3$! But are you sure that $g(n) \in \mathcal{O}(1)$ ? From the definition I have for $\mathcal{O}(x)$, this would mean that $|g(n)|$ is bounded above by a multiple of 1, which is untrue. I still think $g(n) \in \mathcal{O}(n^3)$, but because g(n) takes negative values and is thus illogical, now I don't see how the question be solved even using big-Theta notation?!! – Ryan Mar 26 '12 at 22:32
For any complexity measure, negative is meaningless. And the right definition is that $g(n)$ (not absolute value) is less than a constant times $1$, which it certainly is. Of course if the $-$ is a typo for $+$, the analysis changes. – André Nicolas Mar 26 '12 at 22:37
(On the other hand, it seems that we can easily answer the question by simply taking limits as n approaches infinity -- even though negative complexity is meaningless.) – Ryan Mar 26 '12 at 22:40
You don't need a limit, since $g(n)$ is bounded above by $1$. – André Nicolas Mar 26 '12 at 22:44