Wednesday, January 13, 2010

Why is O(n) Is Pronounced "Big Oh" of n And Why Is "Geek" So Close To "Greek"?

This one is really short, Today, some guy on the internet asked why is the asymptotic form O(n) is pronounced Big Oh? I instantly answered "because we are using the capital letter O to write it".

This answer is wrong, the letter used is the Greek letter Omicron.
So that's why it's pronounced Big Oh!

And the same reason applies to Big Theta, and Big Omega, because of using the Greek letters Theta and Omega represented in the above picture (the second and third figure respectively). It's all coming from the Greeks buddy!
And probably this is also why the word Geek is so close to the word Greek in spelling, I'm not sure about this one though.

1 comment:

kink said...

Why Big O(n)? Because there's a "small o" as well.

Why "Big" and "little" omega? because they're two different concepts as well.

There's only one theta (as far as i'm aware), so calling it Big Theta is unnecessary.

The difference between Big and Small versions is that "small" is asymptotically tight.

For example, if f(n) is O(g(n)), then lim n -> inf (f(n) / g(n)) = c where c is a positive constant

But if f(n) is o(g(n)), then the limit goes to zero.

Suppose your runtime is 2*n^2. then your runtime is O(n^2) but NOT o(n^2). It is, for example o(n^3).