Big O and Big Omega Notations

Discusses the Big O notation with examples

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:

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

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


  • 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 n0.

  • 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[n(n1)2]]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)2 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(n2). We can prove it below:

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

letc=10andn0=10let\: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 > n0.

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

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.