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)=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!

share|improve this question
add comment

2 Answers

up vote 2 down vote accepted

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.

share|improve this answer
    
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
add comment

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

share|improve this answer
    
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
show 5 more comments

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.