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
    How is $g = o(n^3)$?2012-03-26
  • 0
    Oops, you're right. I meant $\Omega(n^3)$, that $n^3$ is a lower bound for $g$.2012-03-26
  • 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
    I really want to see that Algorithm B in operation when $n>101$.2012-03-26
  • 0
    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***?!!2012-03-26
  • 0
    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.2012-03-26
  • 0
    (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.)2012-03-26
  • 0
    You don't need a limit, since $g(n)$ is bounded above by $1$.2012-03-26
  • 0
    Oh, in that case, can you help me reconcile what you said above (about not needing to take absolute values) with the following formal definition of big-O? $f(x) \in \mathcal{O}(g(x)) \Longleftrightarrow |f(x)| \leq M|g(x)|$ for all $x > k$ Thank you so much!2012-03-26
  • 0
    It is not the definition I use. Out of curiosity I checked and noticed it is used by Wikipedia. Not exactly a trustworthy source.2012-03-26
  • 0
    Hmm, yes, Wikipedia, but that's the definition I got from the textbook I'm using: Discrete Mathematics with Applications (3rd edition) by Susanna Epp.2012-03-26
  • 0
    I did a tiny amount of checking, and have seen in the first few hits from Google $f(n)=O(g(n))$ if $0\le f(n)\le kg(n)$ for some $k$, with or without the addition "if $n$ is large enough."2012-03-26
  • 0
    Refer to http://math.stackexchange.com/a/124877/21813 re: the two conflicting definitions of big-O above.2012-03-27