4

I'm preparing for the job interview. One of the topics I'm studing is algorithms analysis, which uses so called Big O notation. So, the problem is, I actually don't know how to properly pronounce those designations, for example, O(n log n). A few more examples here.

The most interesting case is O(n log n), because here we have a function O, multiplication n * log n and logarithm log n together.

Thanks.

7

O(n log n) is typically pronounced "Oh of en log n". The English for big O notation is written out fully as "on the order of...", but when having a technical discussion, abbreviations are perfectly acceptable. However, it's typical to keep of in place to separate the function's identifier from its content. For example, f(3x^2) would be said as "F of three X squared". If you're strictly having a discussion about big O notation, you might omit the of, since the context eliminates the possible ambiguity.

  • 2
    I would include the word "big" to avoid ambiguity between small-oh and big-oh. I would typically pronounce it without the of as well: "big oh en log en" – Paul Feb 5 '15 at 15:50
7

The other answer does a good job of covering the pronunciation of the actual notation, but I would like to add that in some cases you can just call it linearithmic time.

A few useful time complexities and their names:

╔══════════════╦═════════════════╗
║ Complexity   ║ Name            ║
╠══════════════╬═════════════════╣
║ O(1)         ║ constant        ║
║ O(log n)     ║ logarithmic     ║
║ O((log n)^k) ║ polylogarithmic ║
║ O(n)         ║ linear          ║
║ O(n log n)   ║ linearithmic    ║
║ O(n^k)       ║ polynomial      ║
║ O(2^(n^k))   ║ exponential     ║
╚══════════════╩═════════════════╝

(You can find a more complete list on Wikipedia)

  • I would say that these are more widely used than actually pronouncing things like Oh of en log en. They take less cognition to recognize the actual meaning behind them. Now if you were asked to 'compute' the exact time complexity, e.g. O(4n^2), and then simplify, one would pronounce the full notation Oh of four en squared, and then simplify to the algorithm runs in polynomial time. – Chris Cirefice Feb 6 '15 at 2:37

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.