Time Complexity Analysis with Big O Notation

Big O is a type of Asymptotic notation (the other two are: Big Omega and Big Theta). In Math, Asymptotic notations allow you to describe the rate of growth of a function. In Computer Science, Big O is used to describe the performance of an algorithm in terms of the number of operations that need to be executed as the input size grows in the worse case.

Formal Definition of Big O

The formal definition of Big O is:

where:

• c is a constant >0

What does this mean? Let's break it down.

Suppose we have two functions:

• f(n)
• g(n)

We are going to compare these two functions on the basis of their rate of growth. For this we are going to use Big O notation. Let's graph both f(n) and g(n). This is what we get:

Big O notation says that for any point after n₀ the function f(n) will always be ≤ g(n) for larger values approaching ∞. If this condition holds true then we say that f(n)=o(g(n)). Before n₀ though the values of both functions can fluctuate.

Let's go through some worked examples.

Worked Examples

Example 1

Suppose:

• f(n)=10n+200
• g(n)=n₃
• Let c=1

f(n)=o(g(n)) since for larger values approaching ∞ f(n) ≤ g(n).

Example 2

Suppose:

• f(n)=10n+200+n₃
• g(n)=n₃
• Let c=1

f(n) is not o(g(n)) since for larger values approaching ∞ g(n) ≤ f(n).

Example 3

Suppose:

• f(n)=10n+200+n₃
• g(n)=n₃
• Let c=10

f(n)=o(g(n)) since for larger values approaching ∞ f(n) ≤ g(n) where c=10.

References

• Big O notation