Big O and Big Omega Notations

In the previous section, we defined Θ notation. In this section, we'll discuss big O and big Ω notations. The reader would notice the use of the adjective "big" with these notations and rightly suspect that there exist complementary small o and small ω notations, which we'll discuss in the next lesson.

Big O

Big O is expressed as O(g(n)) and is pronounced as "big oh of g of n". We observed that Θ provides both an asymptotically upper and lower tight bound. Big O only provides an asymptotic upper bound which may not necessarily be a tight bound.

Big O is the most commonly talked-about notation when discussing algorithms in industry settings or in interviews. You won't see Θ or other notations being discussed, and for good reason too. Generally, if we are guaranteed that an algorithm will perform no worse than a certain threshold, and that threshold is acceptable for the problem at hand, then knowing its best-case performance or finding a very tight upper bound may not be productive.

Formal Definition

Similar to Θ we define O(g(n)) as a set of functions and a function f(n) can be a member of this set if it satisfies the following conditions:

$$0 \leq f ( n ) \leq c g( n )$$

where c is a positive constant and the inequality holds after n crosses a positive threshold n₀

Explanation

• if f(n) = Θ (g(n)) then it also implies that f(n) = O (g(n))

• The notation means that the function f(n) is bounded by above to within a constant factor of g(n).

• Note that the inequality requires f(n) to be greater than 0 after n crosses n₀.

• The set O(g(n)) may also contain other functions also that satisfy the inequality. There could be several values of c that can be used to satisfy the inequality.

Insertion Sort

Previously, we came up with the following f(n) for the insertion sort algorithm

$$f ( n ) = [ 2 * (n + 1) + 2n ] + [ 2n + 7 [ \frac{n(n-1)}{2} ] ]$$

Now we can attempt to find the O(g(n)) for this expression. As a general rule of thumb, when working with big O we can drop the lower order terms and concentrate only on the higher order terms. The term ^n(n-1)⁄₂ is the highest order term, since it involves a square of n. The above expression is thus quadratic, and we can ignore all the constants and linear terms. Thus a tight bound on the expression would be O(n²). We can prove it below:

$$\frac{n(n-1)}{2}\leq cn^2$$

$$let\:c=10\:and\: n_0\:=10$$

You can always pick a different set of constants as long as it satisfies the inequality for all n > n₀.

As a general rule of thumb, for an expression consisting of polynomials the expression/function is O(the highest polynomial degree in the expression).