Overview

Getting the correct answer is only part of writing a program. A good solution should also remain efficient as its input grows. Big O Notation describes an algorithm's growth rate instead of measuring its exact running time in seconds.

Key concepts

• Time complexity describes how the number of operations grows
• Space complexity describes how much additional memory is needed
• The letter n commonly represents the input size
• Big O makes algorithm comparisons independent of hardware speed

Why do we need Big O Notation?

Two programs may perform similarly with 100 values but behave very differently with one million values. A solution that appears faster for a small test can become much slower at scale. Big O helps compare algorithms according to how their work grows with the input.

What does Big O measure?

Time Complexity

Time complexity describes how the number of operations increases as the input grows. It does not measure seconds because computers and runtime environments have different speeds.

Space Complexity

Space complexity describes how much additional memory an algorithm needs while running. A fast solution may use more memory, while a memory-efficient solution may take longer. Developers choose an appropriate balance for the problem.

Understanding input size

The letter n commonly represents input size. An array containing 10 elements has n = 10; one containing 1,000 elements has n = 1,000. Big O explains how the work changes as n becomes larger.

O(1) — Constant Time

A constant-time algorithm performs the same amount of work regardless of input size. Accessing an array element by index is a common example.

const numbers = [10, 20, 30, 40];

console.log(numbers[0]); // 10

Accessing the first element remains one operation even if the array contains one million values.

O(n) — Linear Time

A linear-time algorithm processes every input element once. If the array doubles in size, the work roughly doubles.

const numbers = [10, 20, 30, 40];

for (let i = 0; i < numbers.length; i++) {
  console.log(numbers[i]);
}

O(n²) — Quadratic Time

Nested loops that each traverse the entire input often produce quadratic complexity. These algorithms can become slow when datasets grow.

const numbers = [1, 2, 3];

for (let i = 0; i < numbers.length; i++) {
  for (let j = 0; j < numbers.length; j++) {
    console.log(numbers[i], numbers[j]);
  }
}

O(log n) — Logarithmic Time

Logarithmic algorithms repeatedly reduce the remaining input. Binary Search, for example, divides a sorted search area in half after every comparison. This allows it to search millions of values with relatively few steps.

O(n log n) — Linearithmic Time

Many efficient sorting algorithms, including Merge Sort and average-case Quick Sort, run in O(n log n). They scale substantially better than O(n²) sorting algorithms on large datasets.

Real-life example: finding a name

Linear Search — O(n)

Imagine starting on the first page of a printed phone book and checking each name until you find the correct one. More pages mean proportionally more work.

Binary Search — O(log n)

Because the phone book is alphabetically sorted, you can open near the middle and discard the half that cannot contain the name. Repeating this process is much faster than checking every entry.

Why isn't exact time used?

The same algorithm may finish sooner on a powerful computer than on an older laptop. Big O ignores these hardware differences and focuses on growth as the input becomes larger, providing a fairer comparison.

Complexities from fastest to slowest

A smaller growth rate is generally more efficient, but the best algorithm still depends on the problem. A slightly slower solution may be easier to understand, simpler to maintain, or use less memory.

Tips for beginners

• Focus on growth instead of memorizing formulas
• Practice identifying loops and nested loops
• Compare multiple solutions to the same problem
• Ask how the code behaves when the input becomes much larger
• Balance efficiency with correctness and readability

Key takeaways

• Big O describes how performance changes as input grows
• Time complexity tracks operations; space complexity tracks additional memory
• O(1) stays constant
• O(log n) repeatedly reduces the problem
• O(n) grows with the input
• O(n²) often comes from nested traversals
• Big O helps developers choose scalable algorithms