Big O Notation

Step 1: What is Big O?

Big O Notation describes the worst-case growth rate of an algorithm's time (or space) as the input size n increases. It does not measure exact time in seconds — it measures how the work scales.

Think of it this way: if you double the input, how much more work does the algorithm do?

Notation	Name	Example	Growth
O(1)	Constant	Array index lookup	Same speed regardless of n
O(log n)	Logarithmic	Binary search	Doubles input, adds 1 step
O(n)	Linear	Loop through array	Doubles input, doubles work
O(n log n)	Linearithmic	Merge sort	Slightly worse than linear
O(n²)	Quadratic	Nested loops	Doubles input, quadruples work
O(2ⁿ)	Exponential	Recursive Fibonacci	Each +1 input doubles work

Analogy: Finding a Name in a Phone Book

Linear scan O(n) — Start at page 1, check every name one by one. With 1,000 pages, you might check all 1,000.

Binary search O(log n) — Open to the middle. Is the name before or after? Discard half. Repeat. With 1,000 pages, you need at most ~10 checks.

Step 2: Growth Curves

Adjust the input size n and watch how the number of operations grows for each complexity class. Toggle curves on/off to compare them.

Input size n: 10

O(1) O(log n) O(n) O(n log n) O(n²)

Step 3: Analyzing Code

Look at each code snippet below and determine its Big O complexity. Select your answer, then reveal the explanation.

Snippet 1 of 5

What is the Big O of this code?

Step 4: Comparison Tool

Pick two algorithms and adjust the input size to see how their operation counts compare. Notice how small differences become dramatic at large n.

Algorithm A

Algorithm B

Input size n: 50

Step 5: Space Complexity

Big O also applies to memory usage. While time complexity measures operations, space complexity measures how much extra memory an algorithm needs as input grows.

Space	Meaning	Example
O(1)	Constant — fixed extra memory	In-place sort (Bubble Sort)
O(n)	Linear — grows with input	Creating a copy of an array
O(n²)	Quadratic — grows with square of input	Building an n x n matrix

Select an algorithm

Time Complexity

O(n²)

Space Complexity

O(1)

Input size n: 8

Memory blocks used: 1

Step 6: Knowledge Check

1. If an algorithm takes the same number of steps regardless of input size, what is its Big O?

O(n) O(1) O(log n) O(n²)

2. A function has two nested loops, each iterating over the full input. What is its time complexity?

O(n) O(2n) O(n²) O(n log n)

3. Binary search on a sorted array of 1,000,000 elements needs at most roughly how many comparisons?

1,000,000 500,000 20 100