2
$\begingroup$

I am learning from the MIT course Introduction to Algorithms.

The professor says:

Now, remember $\Theta(n)$ is essentially something that says "of the order of $n$".

What does "of the order of $n$" mean? Are "of the order of $n$" and "Big O" the same thing?

Please provide the name of any widely recognized textbook that contains detailed explanation about this.

Improve this question
$\endgroup$
1
  • $\begingroup$ @brennn Please don't edit your question so as to try and making the accepted answer "more correct". In the video, the lecturer clearly says "of the order of $n$", not simply "the order of $n$". $\endgroup$
    – dkaeae
    May 20, 2019 at 7:03

2 Answers 2

Reset to default
1
$\begingroup$

the professor mentioned two methods used to measure asymptotic complexity.

$\Theta(n)$ is the order of n.

$O(n)$ is big O of n.

the professor explained

$\Theta(n)$

gives you both the lower bound and an upper bound.

$O(n)$

is just upper bound.

Improve this answer
$\endgroup$
2
  • 5
    $\begingroup$ Theta and Big O are not two different "methods" which "measure" complexity. And the idiom is "on the order of", not "is the order of". The latter means something entirely different. $\endgroup$
    – dkaeae
    May 15, 2019 at 12:07
  • 3
    $\begingroup$ I am one of the downvoters. This seems to somewhat contradict the other answer which I think is more correct in saying that something being "the order of $n$" is not a precise statement. Specifically, one could use the expression to mean $\Theta(n)$, but I think it's too bold to claim that's the intended and generally accepted meaning. Natural language like English might not be precise enough in which case you turn to math. $\endgroup$
    – Juho
    May 15, 2019 at 16:59
8
$\begingroup$

"On the order of" is an informal statement which really only means "approximately". Big O notation is a precise mathematical formulation which expresses asymptotic behavior, not approximate values of a function (e.g., $10n \in O(n)$, despite $10n$ being 10 times as larger as $n$). They can hardly be considered the same things. What the lecturer is trying to do here is supposedly give you some (hand-wavy) intuition as to how Big O notation works, but that should not replace you actually sitting down and learning the precise definitions.

As for your request regarding further reading on Big O notation, (in addition to the linked Wikipedia article) I suggest you take a look at our reference question.

An addendum: After listening to the video again, you can make out the lecturer say "of the order of $n$". This is the British English version of American English "on the order of" and carries the same meaning.

Improve this answer
$\endgroup$
5
  • $\begingroup$ I think that definition 2 of the dictionary you link is closer to the truth, i.e. two functions with the same asymptotic behaviour need not be numerically similar, but are similar in another sense (that is, in their asymptotic behaviour). What the lecturer actually meant is of course another thing entirely... $\endgroup$
    – Discrete lizard ♦
    May 15, 2019 at 11:55
  • $\begingroup$ Point number 2 there reads "on the order of (something)" while point number 1 reads "on the order of (some amount)". One could argue that it is the latter which is the preferred meaning (although as you say, of course, one can only speculate what it is the lecturer actually wants to say). $\endgroup$
    – dkaeae
    May 15, 2019 at 12:03
  • $\begingroup$ Would the downvoter care to comment on their downvote? $\endgroup$
    – dkaeae
    May 15, 2019 at 12:06
  • $\begingroup$ If even experts say "of the order of $n$", then it is apparently the correct expression. Speakers get to decide what is "correct". $\endgroup$
    – Yuval Filmus
    May 20, 2019 at 7:12
  • $\begingroup$ @YuvalFilmus Actually apparently it's British English. Let me correct this since it isn't a mistake. $\endgroup$
    – dkaeae
    May 20, 2019 at 7:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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