Book 01 · Programming FundamentalsPage 6 of 56

Big O Notation

In Turkish: Big O gösterimi

Updated September 30, 20262 min read

In short

Big O notation describes how an algorithm's running time or memory use grows as its input gets larger, focusing on the growth rate rather than exact speed.

What is Big O notation?

Big O notation expresses the efficiency of an algorithm in terms of the size of its input, usually called n. Instead of measuring seconds, which depend on the computer, it describes the growth rate: how much more work the algorithm does when the input doubles or grows tenfold. This makes it possible to compare algorithms independently of hardware or programming language.

The most common complexities, from fastest to slowest, are O(1) constant time, O(log n) logarithmic, O(n) linear, O(n log n), O(n^2) quadratic, and O(2^n) exponential. Looking up an array item by index is O(1), binary search is O(log n), scanning a list is O(n), efficient sorting is O(n log n), and comparing every item with every other item using nested loops is O(n^2).

When calculating Big O, you keep only the fastest-growing term and drop constants, so an algorithm that takes 3n + 5 steps is simply O(n). An everyday analogy: finding a name in a phone book by reading every page is O(n), while opening it in the middle and repeatedly halving the section you search is O(log n). For a phone book of a million names, that is the difference between up to a million checks and about twenty.

Big O is commonly confused with the actual speed of code. It describes how cost scales, not how fast code runs for a particular input, so an O(n) algorithm with a large constant can be slower than an O(n^2) one for small inputs. Strictly speaking, Big O is an upper bound, and developers usually quote the worst case, though average-case figures, such as O(n log n) for quicksort, are also common.

At a glance

Big O compares how fast the work grows with the input, not how fast the code runs today.

Key takeaways

Big O describes how time or memory grows as the input size n increases.
Common classes are O(1), O(log n), O(n), O(n log n), O(n^2), and O(2^n).
Constants and smaller terms are dropped, so 3n + 5 becomes O(n).
It usually describes the worst case and applies to both time and space (memory).
Lower complexity matters most for large inputs; for small inputs, constants can dominate.

Example

Common time complexities in JavaScriptjavascript

const items = [4, 8, 15, 16, 23, 42];
const first = items[0];                             // O(1): one step
const total = items.reduce((sum, x) => sum + x, 0); // O(n): one pass

// O(n^2): nested loops compare every pair of items
function hasDuplicate(list) {
  for (let i = 0; i < list.length; i++) {
    for (let j = i + 1; j < list.length; j++) {
      if (list[i] === list[j]) return true;
    }
  }
  return false;
}
// O(n): a Set keeps only unique values, so compare the sizes
const hasDuplicateFast = (list) => new Set(list).size !== list.length;

Readers ask

What does O(n) mean?

O(n), or linear time, means the work grows in direct proportion to the input size. If an O(n) function takes 1 millisecond for 1,000 items, it will take roughly 10 milliseconds for 10,000 items.

What is the difference between time complexity and space complexity?

Time complexity describes how the number of steps an algorithm takes grows with the input, while space complexity describes how much extra memory it needs. Both are usually expressed in Big O notation, and improving one often costs the other.

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

Yes, for large inputs. O(log n) work grows very slowly, since doubling the input adds only about one extra step, so binary search can find an item among a billion sorted values in about 30 comparisons.