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!

  • 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
    @Ryan: That answer is incorrect. I have made a comment to that answer.2012-03-28