Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
2  
You are right, big-O is often used sloppily, and the relative efficiency does not follow from the big-O statement. –  André Nicolas Mar 26 '12 at 23:08
    
How about setting, say, $F=n^{1,5}$? Then $A\in\mathcal{O}(F)$ but $B\notin\mathcal{O}(F)$. –  rank Mar 27 '12 at 6:15
    
Great Question! –  Kirthi Raman Mar 27 '12 at 12:04

2 Answers 2

up vote 3 down vote accepted

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.

share|improve this answer
    
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)$. –  David Harris Mar 27 '12 at 1:06
    
@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. –  Aryabhata Mar 27 '12 at 1:45
    
@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)$. –  Aryabhata Mar 27 '12 at 1:52
    
@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. –  Ryan Mar 27 '12 at 1:55
    
@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! –  Ryan Mar 27 '12 at 5:16

Maybe the intended answer was along the lines of:

$f \in \mathcal O(n)$ but $g \not \in \mathcal O(n)$, therefore $g$ will grow larger than $f$ for large enough values of $n$.

In which case the question would have been correct.

share|improve this answer
    
@Ryan Why do you think so? It only says "classify". Actually $g\notin\mathcal{O}(F)$ is exactly what you need here. –  rank Mar 27 '12 at 17:49
    
-1: This is incorrect. $f \in O(n)$ and $g \notin O(n)$ does not mean $g$ will grow larger than $f$ for large enough $n$. Consider $f(n) = n$ for all $n$ and $g(n) = n/2$ if $n$ is not prime and $g(n) = n^2$ if $n$ is prime. $g \notin O(n)$, yet $g$ is only less efficient than $f$ on prime input (which are 'sparse': density $0$). Besides, this interpretation is a really a stretch. –  Aryabhata Mar 28 '12 at 15:44
    
@Aryabhata Haha, yes of course! Thanks for another astute observation! –  Ryan Mar 28 '12 at 17:17
    
@Ryan Just consult your professor about the problem. That will settle it. –  rank Mar 28 '12 at 17:45

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.