Big O Notation Visualization

What is Big O Notation?

Big O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. In computer science, it's used to classify algorithms according to how their run time or space requirements grow as the input size grows.

Big O notation characterizes functions according to their growth rates: different functions with the same growth rate may be represented using the same O notation.

Interactive Visualization

Select which complexity functions to display and adjust the input size (n) to see how the number of operations scale.

O(1) - Constant O(log n) - Logarithmic O(n) - Linear O(n log n) - Linearithmic O(n²) - Quadratic O(2ⁿ) - Exponential

Max Input Size (n): 50

Input Size (n)

Operations (Growth Rate)

Common Time Complexities

Notation	Name	Example Algorithms / Operations	Description
O(1)	Constant	Array access (`arr[i]`), Hash table insertion/lookup (average)	The operation takes the same amount of time regardless of the input size.
O(log n)	Logarithmic	Binary search, Balanced BST operations	Time increases very slowly as input size grows. Efficient for large datasets.
O(n)	Linear	Linear search, Traversing an array/list	Time increases directly proportional to the input size.
O(n log n)	Linearithmic	Merge sort, Heap sort, Quick sort (average)	Efficient sorting algorithms. Scales well.
O(n²)	Quadratic	Bubble sort, Selection sort, Nested loops iterating over same data	Time increases significantly with input size. Can become slow quickly.
O(2ⁿ)	Exponential	Recursive Fibonacci (naive), Traveling Salesman (brute force)	Time grows extremely fast. Impractical for anything beyond small inputs.

Real-World Impact

Binary Search - O(log n)

Searching a sorted list of 1,000,000 items:

Linear search (O(n)) might need up to 1,000,000 comparisons.
Binary search (O(log n)) needs at most log₂(1,000,000) ≈ 20 comparisons.

Sorting Algorithms

Sorting 10,000 items:

Selection sort (O(n²)) performs roughly 100,000,000 operations.
Merge sort (O(n log n)) performs roughly 130,000 operations.

Efficient algorithms (like O(n log n)) are crucial for performance on larger datasets.

Nested Loops - O(n²)

Finding duplicate items in a list by comparing every pair:

for i = 0 to n-1:
  for j = i+1 to n-1:
    if list[i] == list[j]:
      return True // Found duplicate

This nested loop structure results in O(n²) complexity.