Big O Complexities — From Best to Worst
| Notation | Name | n=10 | n=1,000 | n=1,000,000 |
|---|---|---|---|---|
| O(1) | Constant | 1 | 1 | 1 |
| O(log n) | Logarithmic | 3 | 10 | 20 |
| O(n) | Linear | 10 | 1,000 | 1,000,000 |
| O(n log n) | Linearithmic | 33 | 10,000 | 20,000,000 |
| O(n²) | Quadratic | 100 | 1,000,000 | 10¹² |
| O(2ⁿ) | Exponential | 1,024 | 10³⁰¹ | Uncomputable |
O(1) — Constant Time
The operation takes the same time regardless of input size.
O(log n) — Logarithmic
The problem is halved with each step. Extremely efficient at scale — 1 million items needs only ~20 steps.
O(n) — Linear
One operation per element. Double the input, double the time.
O(n log n) — Linearithmic
Common in efficient sorting algorithms. n items × log n work per item.
O(n²) — Quadratic
Usually caused by nested loops over the same data. Becomes painfully slow at n > 10,000.
Common Data Structure Time Complexities
| Data Structure | Access | Search | Insert | Delete |
|---|---|---|---|---|
| Array | O(1) | O(n) | O(n) | O(n) |
| Linked List | O(n) | O(n) | O(1)* | O(1)* |
| HashMap | N/A | O(1) avg | O(1) avg | O(1) avg |
| Binary Search Tree | O(log n) | O(log n) | O(log n) | O(log n) |
| Heap (min/max) | O(1) top | O(n) | O(log n) | O(log n) |
| Stack / Queue | O(n) | O(n) | O(1) | O(1) |
*Linked list insert/delete at a known node position
Rules for Calculating Big O
- Drop constants: O(2n) = O(n), O(500) = O(1)
- Drop smaller terms: O(n² + n) = O(n²)
- Different variables stay separate: Iterating m items then n items = O(m + n), not O(n)
- Nested loops multiply: O(n) inside O(n) = O(n²)
- Sequential loops add: O(n) then O(n) = O(n), not O(n²)
💡 Interview Tip
Always state both time and space complexity. For recursive solutions, space complexity includes the call stack depth — a recursive solution with n recursive calls has at minimum O(n) space complexity. Iterative solutions typically have O(1) space.
How We Research and Update This Guide
We test the underlying formula or workflow, compare outputs with reliable references, and revise examples whenever the page content changes.
- The workflow or formula is tested directly in the tool and compared against independent reference examples.
- Examples are kept practical so readers can verify the result without hidden assumptions.
- Pages are revised whenever the interface, calculation flow, or surrounding guidance materially changes.
Frequently Asked Questions — Big O Notation
Big O notation describes how an algorithm's performance (time or memory) scales as the input grows. It answers: "If I double the input size, how much slower does this code get?" O(1) means constant — same speed regardless of input. O(n) means linear — twice the input takes twice as long. O(n²) means quadratic — twice the input takes four times as long. Big O focuses on the worst case and ignores constants (O(2n) = O(n) in Big O).
Big O describes asymptotic behaviour — how things scale at large n, not exact runtime. At large n, constants become irrelevant. Whether an algorithm takes 2n or 5n steps, both are O(n) — if you double n, both double. Whether it takes n or 1000n, for n = 1 million both grow the same way. The constant matters for practical performance tuning, but for comparing algorithm scalability, the growth pattern (linear, quadratic, logarithmic) is what matters.
Time complexity measures how the number of operations grows with input size. Space complexity measures how the memory usage grows with input size. An algorithm can trade one for the other — caching results (memoisation) uses extra space to save time. When people say "Big O of an algorithm", they usually mean time complexity. In interviews, you are often expected to state both.
O(log n) means the algorithm halves the problem with each step. Binary search is the classic example: to find a value in a sorted array of 1000 elements, you need at most 10 steps (log₂ 1000 ≈ 10). Double to 2000 elements? Only 11 steps. This is why sorted data + binary search beats linear search dramatically at scale. Balanced BST operations (insert, search, delete) are also O(log n).
Rules: (1) Loops over n → O(n). (2) Nested loops over n → O(n²). (3) Dividing problem in half each step → O(log n). (4) Loop + divide → O(n log n). (5) Keep only the dominant term — O(n² + n) = O(n²). (6) Drop constants — O(3n) = O(n). (7) For recursion, use the recurrence relation or Master theorem. Practical tip: look for the loop structure first — it tells you 80% of the story.
Constant-time O(1) operations: Array/list index access (arr[i]), HashMap/HashSet get/put/contains (average case), Stack push/pop, Queue enqueue/dequeue, Linked list insert/delete at known node. Non-constant: HashMap worst case is O(n) with hash collisions (rare with good hash functions). Sorted array search is O(log n) with binary search. Unsorted search is O(n).