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: BigOh and LittleOh and BigOmega and LittleOmega. This article describes an easy but useful mnemonic that can be used to differentiate between the three main classes. BigOh and LittleOh 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 Omicron. 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).
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 (LittleOh). I use
the same mnemonic for this one as for the BigOh, 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.
BigOmega and LittleOmega This mnemonic is a bit easier since the Greek letter is already used. To access it, read the Omega as Omega. 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))
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 (LittleOmega). I use the same mnemonic for this one as for the BigOmega, 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. BigTheta 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.
As there’s no such thing as LittleTheta, there’s no confusion possible on which to use.
Have a Linux Problem
Linux Books
Linux Home: Linux System Administration Hints and Tips (c) www.gotothings.com All material on this site is
Copyright.
