Big O Notation

• Measures how runtime scales with input size
• Important to note that O() notation is not everything
  • Its important to consider how algorithms work in the memory/rest of the system

O(1)

• Constant runtime

• Accessing an array by index

• Access a hash table

O( log(n) )

• Logarithmic time

• Runtime increases slowly as input grows

• Binary search on sorted array

• performing operations on a balanced binary tree

0(n)

• Linear time

• Runtime grows with input as each element is touched once

• Finding minimax elements in an unsorted array

• Checking if an element exists in an unsorted array

O(nlogn)

• Linearithmic time

• Runtime of most efficient sorting algorithms (merge sort, quick sort, heap sort)

O(n${}^2$)

• Quadratic runtime

• Bubble sort

• Nested loops

O(n${}^3$)

• Cubic runtime

• Naïve matrix multiplication

• Triple nested loops

O(2${}^n$)

• Exponential runtime

• Recursive algorithms

O(n!)

• Factorial runtime

• Permutation-generation problems

  • Very inefficient for trivial input size

Array Access

• Although accessing a 2D array is O(n${}^2$)
  • Accessing by rows is faster than accessing by columns!
• Reading row-wise maximises sequential access
  • More cache friendly

Linked list us Array

• Both are linear time
• Accessing an array is faster
  • Array elements are closer together
  • Linked-list nodes are often scattered in memory