Big O Notation

Introduction

Big O notation is a mathematical notation for describing the complexity of an algorithm. Time and space complexity are two things we care about when it comes to designing algorithms.

Worst Case

$\Omega(n)$ is the best case complexity of an algorithm. $\theta(n)$ is the average case complexity of an algorithm. $\Omicron(n)$ is the worst case complexity of an algorithm.

O(n)

The time complexity of the following code is $\Omicron(n)$.

def print_items(n):
    for i in range(n):
        print(i)

print_items(10)

Drop Constant

The constant can be dropped from the expression. For example, $\Omicron(2n)$ can be rewritten as $\Omicron(n)$.

def print_items(n):
    for i in range(n):
        print(i)

    for j in range(n):
        print(j)

print_items(10)

O(n^2)

The time complexity of the following code is $\Omicron(n^2)$.

def print_items(n):
    for i in range(n):
        for j in range(n):
            print(i,j) 

print_items(10)

The following code runs for $\Omicron(n^3)$ time.

def print_items(n):
    for i in range(n):
        for j in range(n):
            for k in range(n):
                print(i,j,k)

print_items(10)

$\Omicron(n^3)$ (and so on) can be simplified to $\Omicron(n^2)$.

Drop non-dominants

The time complexity of the following code is $\Omicron(n^2+n)$.

def print_items(n):
    for i in range(n):
        for j in range(n):
            print(i,j)
    for k in range(n):
        print(k)

print_items(10)

We can drop the non-dominant term n, therefore the time complexity is $\Omicron(n^2)$.

O(1)

$\Omicron(1)$ means the time complexity is constant, i.e., no matter how large the input size is, the time complexity is always the same.

def add_items(n):
    return n + n + n

print add_items(10)

O(log n)

Binary search is an example of an algorithm that has time complexity of $\Omicron(\log n)$.

Different Terms for Inputs

def print_items(a,b):
    for i in range(a):
        print(i)

    for j in range(b):
        print(j)

print_items(1, 10)

The above function has two parameters, a and b, and the time complexity is $\Omicron(a+b)$. It can not be simplified to $\Omicron(a)$ or $\Omicron(b)$.

Lists

• $\Omicron(1)$: my_list.append(item), my_list.pop(), my_list.lookup(index)
• $\Omicron(n)$: my_list.pop(n), my_list.insert(n, item), my_list.remove(item), my_list.lookup(item) (because the list needs to be reindexed)

Wrap up

Please refer to this cheat sheet for more details.