What are the difference between Big Oh, Big Omega and Big Theta?

The difference between Big Oh, Big Omega and Big Theta.

This is written not from the mathematical point of view, but the information technology point of view, so there won’t be any mathematical things in this article. I also will not handle complexity in greater detail than necessary.

Algorithm complexity studies the limiting behaviour of algorithms as the input n approaches infinity. There are three main complexity classes in which algorithms can be placed: Oh, Omega and Theta. Two of them, Oh and Omega can be divided in subclasses: Big-Oh and Little-Oh and Big-Omega and Little-Omega.

This article describes an easy but useful mnemonic that can be used to differentiate between the three main classes.

Big-Oh and Little-Oh

This one helps if you know that the letter is not actually a capital ‘o’, but the Greek capital Omicron. The Omicron looks deceptively much like the capital ‘o’: O. The mnenomic lies in the name of the Greek letter.

To access the mnemonic, Omicron should be read as O-micron. Extended to a sentence, you get: ‘… is micro compared to … as n approaches infinity’.

Let’s take, for example, the following notation:

f(n) €  (g(n))

Using the mnenomic, the following can be read: “The function f is micro compared to g as n approaches infinity.” This means that, as n approaches infinity, f is asymptotically bounded above by g (up to a constant factor).
Or: f(n) € g(n)  k as n approaches infinity.

Be mindful that this means that f(n) could very well equal g(n) for some constant factor as n approaches infinity.

If the two should not be equal, use the tighter o (Little-Oh). I use the same mnemonic for this one as for the Big-Oh, but as the hole in the letter is tighter, it reminds me that o describes a tighter bound which is strictly smaller than its bound.
This corresponds with the definition of f(n) € (g(n)): g(n) asymptotically dominates f(n), or, more mathematically: f(n) < g(n) . k.

Big-Omega and Little-Omega

This mnemonic is a bit easier since the Greek letter is already used. To access it, read the Omega as O-mega. Extended to a sentence form, you can read ‘… is mega compared to … as n approaches infinity.’

Let’s take, for example, the following notation:

f(n) € (g(n))
Using the mnemonic, the following can be read: “The function f is mega compared to g as n approaches infinity.” This means that, as n approaches infinity, f is asymptotically bounded below by g (up to a constant factor).
Or: f(n) € g(n)  k as n approaches infinity.

Be mindful that this means that f(n) could very well equal g(n) for some constant factor as n approaches infinity.

If the two should not be equal, use the tighter (Little-Omega). I use the same mnemonic for this one as for the Big-Omega, but as the hole in the letter is smaller, it reminds me that w describes a tighter bound which is strictly smaller than its ñ bound.

This corresponds with the definition of f(n) € w (g(n)): f(n) asymptotically dominates g(n), or, more mathematically: f(n) > g(n) . k.

Big-Theta

There’s no real mnemonic for this one, but when f(n) grows just as fast as g(n) asymptotically, then f(n) € (g(n)). Should the other two mnemonics fail, then the function you’re trying to evaluate is most likely in this class.
Informally, use this when the asymptotic growth of two functions is equal.

As there’s no such thing as Little-Theta, there’s no confusion possible on which to use.

Have a Linux Problem
Linux Forum - Do you have a Linux Question?

Linux Books
Linux Certification, System Administration, Programming, Networking Books

Linux Home: Linux System Administration Hints and Tips