Big-O Notation Visualizer -- Compare Algorithm Complexity Curves

What is Big-O Notation?

Big-O notation describes how an algorithm's runtime or space requirements grow as the input size increases. It focuses on the dominant term and ignores constants and lower-order terms.

For example, if an algorithm takes 3n^2 + 5n + 10 operations, the Big-O is O(n^2). The n^2 term dominates as n grows large, so the constants (3) and lower terms (5n, 10) are dropped.

Big-O gives an upper bound on growth rate. It tells you the worst-case scenario -- how badly the algorithm can perform as input size increases.

Complexity Classes Explained

O(1) -- Constant Time

The algorithm takes the same amount of time regardless of input size. Array access by index, hash table lookup, and stack push/pop are all O(1).

Examples: array[5], hashmap.get(key), stack.push(x)

O(log n) -- Logarithmic Time

The algorithm divides the problem in half at each step. Binary search is the classic example: each comparison eliminates half the remaining elements.

For n=1000, log2(1000) is about 10. For n=1,000,000, log2 is only about 20. This is extremely efficient even for huge inputs.

Examples: binary search, balanced tree lookup

O(n) -- Linear Time

The algorithm processes each element once. Doubling the input doubles the time. Linear search, single loops, and simple traversals are O(n).

Examples: linear search, array sum, finding max element

O(n log n) -- Linearithmic Time

The algorithm divides the problem (log n) but does linear work at each level. This is the best possible time complexity for comparison-based sorting.

Merge sort and heap sort are O(n log n). For n=1000, that is about 10,000 operations. For n=1,000,000, it is about 20,000,000 -- much better than O(n^2).

Examples: merge sort, heap sort, quicksort (average case)

O(n^2) -- Quadratic Time

The algorithm uses nested loops. For each element, it processes all elements again. Doubling the input quadruples the time.

Bubble sort, insertion sort, and selection sort are all O(n^2). For n=1000, that is 1,000,000 operations. For n=10,000, it is 100,000,000 -- this quickly becomes impractical.

Examples: bubble sort, selection sort, naive nested loops

O(n^3) -- Cubic Time

Three nested loops. Matrix multiplication (naive algorithm) and some graph algorithms are O(n^3). For n=100, that is 1,000,000 operations. For n=1000, it is 1,000,000,000.

Examples: naive matrix multiplication, Floyd-Warshall algorithm

O(2^n) -- Exponential Time

The algorithm explores all possible combinations. Each additional input doubles the time. Recursive algorithms that make two calls per level (like naive Fibonacci) are O(2^n).

For n=20, that is about 1 million operations. For n=30, it is over 1 billion. For n=40, it is over 1 trillion. Exponential algorithms become unusable very quickly.

Examples: recursive Fibonacci, subset generation, brute-force subset sum

O(n!) -- Factorial Time

The algorithm explores all permutations. Factorial growth is the fastest growth rate in common use. Even for n=10, n! is 3,628,800. For n=15, it is over 1 trillion.

Brute-force solutions to the traveling salesman problem are O(n!). These algorithms are only viable for tiny inputs.

Examples: brute-force traveling salesman, generating all permutations

Common Misconceptions

Big-O Is Not Exact Runtime

Big-O describes growth rate, not actual time. An O(n) algorithm might be slower than an O(n^2) algorithm for small n if the constants are large. Big-O only matters as n grows.

Constants and Lower Terms Are Dropped

An algorithm that takes 100n + 500 operations is O(n), not O(100n). An algorithm that takes n^2 + 1000n is O(n^2). Only the dominant term matters.

Big-O Is Worst Case

Big-O describes the worst-case scenario unless otherwise specified. Quicksort has O(n log n) average case but O(n^2) worst case. When someone says "quicksort is O(n log n)," they mean average case.

Space Complexity Also Uses Big-O

Big-O applies to memory usage too. An algorithm that creates an array of size n has O(n) space complexity. Recursive algorithms that go n levels deep have O(n) stack space.

Frequently Asked Questions

What is Big-O notation?

Big-O notation describes the upper bound of an algorithm's growth rate as input size increases. O(n) means the algorithm's time grows linearly with input size. O(n^2) means it grows quadratically. It focuses on the dominant term and ignores constants.

What is the difference between O(n) and O(n log n)?

O(n) grows linearly -- doubling input doubles the work. O(n log n) grows slightly faster because of the log n factor. For n=1000, O(n) is 1000 operations while O(n log n) is about 10000. The difference becomes more significant as n grows.

Why is O(n^2) considered bad?

O(n^2) means operations grow as the square of input size. For n=100 that is 10000 operations, but for n=10000 that is 100000000 (100 million). Even fast computers struggle with O(n^2) algorithms on large inputs, which is why O(n log n) algorithms are preferred.

What does O(1) mean?

O(1) means constant time -- the algorithm takes the same time regardless of input size. Accessing an array by index is O(1): whether the array has 10 elements or 10 million, it takes the same time to retrieve array[5].

Is O(log n) better than O(n)?

Yes. O(log n) is much better than O(n) for large inputs. Binary search is O(log n) -- for n=1,000,000 it takes only about 20 comparisons. Linear search is O(n) and would take up to 1,000,000 comparisons.

What is the best sorting algorithm complexity?

O(n log n) is the best possible time complexity for comparison-based sorting. Merge sort, heap sort, and quicksort (average case) are all O(n log n). No comparison-based sort can do better in the general case.

Why do we ignore constants in Big-O?

Constants become irrelevant as input grows. An algorithm that takes 100n operations is technically 100x slower than one that takes n, but both are O(n). For large enough n, an O(n log n) algorithm will beat even a 1000n algorithm because log n eventually dominates any constant.

Does this tool store any data?

No. All visualizations run entirely in your browser using JavaScript and Canvas 2D. No data is sent to any server.

Related Tools

• Sorting Algorithm Visualizer -- see merge sort, quicksort, bubble sort in action
• Recursion Visualizer -- visualize recursive call trees
• Data Structure Visualizer -- arrays, linked lists, trees, graphs
• Hash Table Visualizer -- explore hash functions and collision resolution

Big-O Notation Visualizer FAQ