Big O Notation

• Measures how runtime scales as input size grows

Ascending order of runtime length:

1. O(1)
2. O(log[n])
3. O(n)
4. O(nlog[n])
5. O(n${}^2$)
6. O(2${}^n$)
7. O(n!)

• Just because two algorithms have the same O() runtime, does not mean they will run at the same speed
  • You must consider how the memory is used
• Arrays are faster to access than Linked-lists
• When accessing arrays, reading by rows are faster than reading by column