6
$\begingroup$

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!

  • 2
    You are right, big-O is often used sloppily, and the relative efficiency does not follow from the big-O statement.2012-03-26
  • 0
    Great Question!2012-03-27

1 Answers 1

3

You are right! and kudos for asking this question.

It is annoying when people (including many folks in teaching positions) use BigOh completely wrong, for example, phrases like: Algorithm A is better than $O(n^2)$ which is nonsense and shows a lack of understanding of either BigOh, or what an asymptotic upper bound means. What is worse is that sometimes you are forced to use it sloppily yourself in order not to confuse matters when talking with such folks.

Note that, even though talking in terms of $\Theta$ works in this case, it will not always do.

For instance: $f(n) = n^2$ and $g(n) = 2n^2$, both are $\Theta(n^2)$, but you can still say that $A$ is more efficient.

Also one should be aware of the definition of BigOh/$\Theta$ that is being used. The typical Computer Science definition does not involve the absolute value, but the mathematical (Landau) definition does.

  • 0
    I want to defend this abuse of the terminology. Sometimes you have an algorithm whose worst case behavior is $\Theta(n^2)$. It would not be correct to say this algorithm has running time $\Theta(n^2)$, because not all inputs will elicit this. So here, the term $O(n^2)$ means that the algorithm is among the class of algorithms with worst-case behavior $O(n^2)$.2012-03-27
  • 0
    @DavidHarris: I don't see your point. Saying an algorithm is $O(n^2)$ when the worst case is quadratic is a perfectly valid usage. In fact, saying it is $\Theta(n^2)$ would be wrong for the reasons you state (unless one mentions they are talking about the worst case). The example I gave was: "Algorithm A is _better than_ $O(n^2)$", which is meaningless. I don't see how your comment supports that.2012-03-27
  • 0
    @David: Note: I am talking about the case when people are speaking about sub-qudaratic algorithms (not worst case quadratic) and say that those algorithms are _better than_ $O(n^2)$.2012-03-27
  • 0
    @DavidHarris I don't think "Alg A is $\mathcal{O}(g)$" means "the worst-case order of Alg A is $g$". (Hopefully, I'm not misunderstanding your point.) If the best/average/worst-case complexity functions of Alg A are different, each *can* separately have their own $\mathcal{O}$, $\Omega$ and $\Theta$. ps. I'm assuming you're not David Harris the Aussie actor, haha.2012-03-27
  • 0
    @Aryabhata Oh, that clears up the confusion between Andrea and I in the discussion of version-1-of-this-question that was posted prior to this. And thanks for the good observation that even Θ can be inadequate to imply relative efficiency (due to the constant multiple)! Finally, i agree that students shouldn't have to dumb down or deliberately use sloppy or even wrong notation/presentation/reasoning during assessment to cater to certain marking schemes. I've sometimes been too idealistic/stubborn, and I pay the price!2012-03-27
  • 0
    @Ryan: You are welcome! You can and should educate the party concerned :-)2012-03-27
  • 0
    @Ryan: That answer is incorrect. I have made a comment to that answer.2012-03-28