3
$\begingroup$

I first learned about the Big O notation in an intro to Algorithms class. He showed us that function $g \in O(f(n))$
Afterwords in Discrete Math another Professor, without knowing of the first, told us that we should never do that and that it should be done as $g \in O(f)$ where g and f are functions. The question is which one of these is right, why, and if they both are, what is the difference?

$\endgroup$
3
  • $\begingroup$ I personally doubt there is any difference. I would ask the second professor why not. $\endgroup$
    – usul
    Mar 21 '14 at 18:51
  • 1
    $\begingroup$ In theory, $f$ could be a function which maps integers to functions and $f(n)$ could refer to the function which is the value of $f$ at $n$. In practice, this will never be the case and the notation will always be unambiguous, therefore your discrete mathematics professor is being pedantic - not an uncommon fault among professors. One of the most valuable things you can learn at school is that, sometimes, smart people in positions of authority get stuff wrong. It's the human condition. $\endgroup$
    – Patrick87
    Mar 21 '14 at 18:58
  • $\begingroup$ @Patrick87 "In practice, this will never be the case and the notation will always be unambiguous" -- hahaha, that's a good one. XD "being pedantic - not an uncommon fault among professors" -- we have to disagree on that judgement. I personally prefer pedants using calculated sloppiness as appropriate over people who can't handle/provide any amount of precision. (Also, why does pedantic equal wrong?) $\endgroup$
    – Raphael
    Mar 21 '14 at 21:05
4
$\begingroup$

There are two views on this, formal and pragmatic.

Formally, you always have $O(f(n)) = O(1)$ as long as $f : \mathbb{N} \to \mathbb{N}$ since $f(n)$ is just a number, i.e. a constant function. $O(f)$, on the other hand, does what you want.

However, you often want to indicate which variable goes to infinity¹. If you let $f : x \mapsto x^2$ and state

$\qquad\displaystyle 2n + k \in O(f)$,

which variable should identify with $x$? Writing

$\qquad\displaystyle 2n + k \in O(f(n))$

can be used (given mutual understanding) to clarify.

Personally, I'd propose to use

$\qquad\displaystyle 2n + k \in O(f)$ for $n \to \infty$

or

$\qquad\displaystyle 2n + k \in O_n(f)$.

However, use of Landau notation is (sadly) not meant to be rigorous most of the time², but is instead used as a lazy shortcut.


  1. Never mind that Landau notation gets into trouble when two independent variables are around, anyway.

  2. Meaning that many people use it in a sloppy way. Not saying that that's a good thing. Many questions on this site are based in wrong understanding of terms that are founded in teachers promoting sloppiness in the name of (alleged) clarity (imho).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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