Question 1

What is Big O notation?

Accepted Answer

Big O describes how an algorithm's resource usage (time or space) grows as input size grows. O(n) means linear: 10x input → 10x time. O(n²) means quadratic: 10x input → 100x time. O(1) means constant: same time regardless of input. It's an upper bound on growth rate, ignoring constants and lower-order terms, useful for comparing scaling behavior, not absolute speed.

Question 2

Why do we ignore constants in Big O?

Accepted Answer

Because the point of Big O is scaling behavior, not absolute performance. An algorithm that takes 5n + 100 milliseconds and one that takes 2n + 50 ms are both O(n), they scale linearly. As n grows large, the constants stop mattering compared to the linear growth. For small n, constants do matter, which is why insertion sort (O(n²)) can beat merge sort (O(n log n)) for very small arrays despite worse Big O.

Question 3

What's the difference between best, average, and worst case?

Accepted Answer

Same algorithm, different inputs. Quicksort: best/average O(n log n), worst O(n²) when the pivot is consistently bad. Hash table lookup: average O(1), worst O(n) when all keys collide. Big O usually refers to worst-case unless specified. Average case requires assumptions about input distribution. Best case is rarely useful, knowing the lower bound doesn't help when planning for real workloads.

Question 4

Is O(log n) always faster than O(n)?

Accepted Answer

For large n, yes, log grows much slower. For small n, the constants in front of the log might make O(log n) actually slower. Example: binary search has logarithmic complexity but requires sorted data. For a 5-element list, linear search is faster than binary search even though linear is O(n). Big O tells you about scaling, not constants.

Question 5

What does O(n log n) actually mean?

Accepted Answer

Each element gets processed log n times, typical of divide-and-conquer algorithms. Merge sort: divides the array log n times (each level halves), and at each level processes all n elements once. n elements × log n levels = n log n total work. It's the asymptotic minimum for comparison-based sorting. Heapsort, mergesort, and quicksort (average) all achieve it.

Question 6

Why is hash map lookup O(1) but linked list lookup O(n)?

Accepted Answer

Hash map computes hash(key) → index, jumps directly there. Constant time (assuming low collision rate). Linked list has no index, to find the kth element, walk k pointers from the head. Linear in position. The trade-off: hash maps don't preserve insertion order easily and have high constant overhead per operation. Linked lists are simple and pointer-walk efficient but slow for random access.

Question 7

What complexities are practically usable?

Accepted Answer

O(1), O(log n), O(n), O(n log n), all fine for any realistic input. O(n²), works for n < 10,000 in most contexts; painful above. O(n³), only for very small inputs (n < 1,000). O(2ⁿ), O(n!), only solvable for n < 30, and only with optimization. If your algorithm is exponential, you usually need a different algorithm, heuristic, approximation, or polynomial-time alternative.

Question 8

Is this cheatsheet always current?

Accepted Answer

Algorithm complexities are mathematical properties, they don't change. The complexity of quicksort has been O(n log n) average since Hoare published it in 1961. New algorithms occasionally improve known bounds (matrix multiplication has been gradually improving below O(n^2.37)), but for the algorithms in this cheatsheet, the values are stable.

Question 9

What standards does Big O Complexity Cheatsheet validate against?

Accepted Answer

Big O Complexity Cheatsheet checks compliance with Algorithm complexity theory.

Question 10

What are the limitations of Big O Complexity Cheatsheet?

Accepted Answer

Complexity classes are theoretical, actual performance depends on constants Does not cover all data structure variants

Notation	Name	10 Items	1M Items	Practicality
O(1)	Constant	1 op	1 op	Ideal
O(log n)	Logarithmic	3 ops	20 ops	Excellent
O(n)	Linear	10 ops	1M ops	Good
O(n log n)	Linearithmic	33 ops	20M ops	Scalable
O(n²)	Quadratic	100 ops	10¹² ops	Slow @ Scale

Big O Complexity Cheatsheet

Big O Complexity Cheatsheet

Time Complexity

Space Complexity

Learn More

Base64 Encoding: When You Should and Shouldn't Use It (2026 Guide)

Cron Expression Syntax Explained (with 50 Examples) — 2026 Guide

The Complete HTTP Status Code Cheatsheet (2026)

What is Big O Complexity Cheatsheet?

Frequently Asked Questions

Technical Deep Dive

Big O Complexity Cheatsheet

Built for Devs

Smart Defaults

Workflow-Friendly

01 Growth Scale Matrix

02 Algorithm Optimization Pipeline

Runs 100% in your browser

You Might Also Need

Git Commit Message Generator

Regex Explainer

AI Code Review Assistant

API Client Code Generator