What Is Big O Notation? Explained With Examples

Big O notation describes how the running time (or memory usage) of an algorithm grows as the size of its input grows, focusing on the dominant term and ignoring constant factors — it describes a worst-case growth trend, not an exact time.

Common causes

• Comparing algorithms by actual runtime on a specific machine isn't meaningful across hardware — Big O provides a hardware-independent way to reason about scalability as input size increases

How to fix it

• O(1) — constant time: the operation takes the same time regardless of input size, like accessing an array element by index
• O(n) — linear time: time grows proportionally with input size, like a single loop over an array
• O(log n) — logarithmic time: time grows slowly as input grows, typical of algorithms that repeatedly halve the problem, like binary search
• O(n^2) — quadratic time: time grows with the square of input size, typical of nested loops comparing every pair of elements

Example

// O(n) — one loop
for (let i = 0; i < arr.length; i++) { ... }

// O(n^2) — nested loop
for (let i = 0; i < arr.length; i++) {
  for (let j = 0; j < arr.length; j++) { ... }
}

FAQ

Does Big O tell you the exact runtime?

No — it describes how runtime scales as input grows, ignoring constant factors and lower-order terms. An O(n) algorithm with a large constant factor can be slower than an O(n log n) one for small inputs.