Lesson 03
Understanding Big-O Notation
A clear guide to measuring how algorithm runtime and memory usage scale as your input grows.
What is Big-O Notation?
Big-O notation is a mathematical framework used by computer scientists to describe how an algorithm performs. Rather than measuring exact execution time in seconds (which varies depending on computer hardware), Big-O measures how the number of required operations grows relative to the input size.
Common Time Complexities
Here are the fundamental growth rates you will encounter when studying algorithms, ordered from fastest to slowest:
- O(1) Constant Time: The algorithm always takes the exact same number of steps regardless of dataset size. Example: Accessing an array item by index.
- O(log n) Logarithmic Time: Execution time grows slowly as the dataset doubles. Example: Binary Search.
- O(n) Linear Time: Execution time grows at a direct 1-to-1 ratio with input size. Example: Linear Search.
- O(n log n) Linearithmic Time: Common for efficient sorting algorithms. Example: Merge Sort and Quick Sort.
- O(n²) Quadratic Time: Performance drops significantly as dataset size increases because of nested loops. Example: Bubble Sort.
Big-O Comparison Cheat Sheet
Use this reference table to evaluate algorithm efficiency at a glance:
| Big-O Notation | Name | Performance Rating | Example Operation |
|---|---|---|---|
| O(1) | Constant | Excellent | Array lookup by index |
| O(log n) | Logarithmic | Good | Binary Search |
| O(n) | Linear | Fair | Linear Search |
| O(n log n) | Linearithmic | Acceptable | Merge Sort |
| O(n²) | Quadratic | Horrible | Bubble Sort |