Big-O, Little-o, Theta, Omega
Big-O, Little-o, Omega, and Theta are formal notational methods for stating the growth of resource needs (efficiency and storage) of an algorithm. There are four basic notations used when describing resource needs. These are: O(f(n)), o(f(n)), , and . (Pronounced, Big-O, Little-O, Omega and Theta respectively)
Formally:
" is " iff for some constants and , for all
" is " iff for some constants and , for all
" is " iff is AND is
" is " iff is AND is NOT
Informally:
" is " basically means that describes the upper bound for
" is " basically means that describes the lower bound for
" is " basically means that describes the exact bound for
" is " basically means that is the upper bound for but that can never be equal to
Another way of saying this:
" is " growth rate of <= growth rate of
" is " growth rate of >= growth rate of
" is " growth rate of == growth rate of
" is " growth rate of < growth rate of
An easy way to think about big-O
The math in big-O analysis can often be intimidates students. One of the simplest ways to think about big-O analysis is that it is basically a way to apply a rating system for your algorithms (like movie ratings). It tells you the kind of resource needs you can expect the algorithm to exhibit as your data gets bigger and bigger. From best (least resource requirements ) to worst, the rankings are: , , , , , , . Think about the graphs in the grow rate section. The way each curve looks. That is the most important thing to understand about algorithms analysis
What all this means
Let's take a closer look a the formal definition for big-O analysis
" is " if for some constants and , for all
The way to read the above statement is as follows.
n is the size of the data set.
is a function that is calculated using n as the parameter.
means that the curve described by is an upper bound for the resource needs of a function.
This means that if we were to draw a graph of the resource needs of a particular algorithm, it would fall under the curve described by . What's more, it doesn't need to be under the exact curve described by . It could be under a constant scaled curve for ... so instead of having to be under the curve, it can be under the curve or the curve. In fact it can be any constant, as long as it is a constant. A constant is simply a number that does not change with n. So as gets bigger, you cannot change what the constant is. The actual value of the constant does not matter though.
The other portion of the statement means that does not need to be true for all values of . It means that as long as you can find a value for which is true, and it never becomes untrue for all larger than , then you have met the criteria for the statement is
In summary, when we are looking at big-O, we are in essence looking for a description of the growth rate of the resource increase. The exact numbers do not actually matter in the end.
Last updated