Big O Complexity Visualizer

Help

What is Big O Notation?

Big O describes how an algorithm's runtime or space requirements grow as input size increases
It focuses on the worst-case scenario and ignores constant factors
Lower complexity = better performance for large inputs

Complexity Classes Explained

O(1) - Constant: Same time regardless of input size (array access, hash table lookup)
O(log n) - Logarithmic: Divides problem in half each step (binary search)
O(n) - Linear: Grows proportionally with input (linear search, single loop)
O(n log n) - Linearithmic: Efficient sorting algorithms (merge sort, quick sort)
O(n²) - Quadratic: Nested loops (bubble sort, selection sort)
O(n³) - Cubic: Triple nested loops (naive matrix multiplication)
O(2ⁿ) - Exponential: Doubles with each additional input (recursive fibonacci, subset generation)

Real-World Examples

O(1): Looking up a value in a dictionary/hash map
O(log n): Finding a name in a phone book using binary search
O(n): Checking if an item exists in an unsorted list
O(n log n): Sorting a list efficiently (Python's sorted(), Java's Arrays.sort())
O(n²): Comparing every student's grade with every other student
O(2ⁿ): Finding all possible subsets of a set