Two algorithms can solve the same problem very differently in speed. Big-O notation describes how an algorithm’s time or memory use grows as the input size n grows, ignoring machine speed and small details.

Reading Big-O

Big-O gives an upper bound on growth, normally for the worst case. You keep only the fastest-growing term and drop constants. An algorithm that does 3n^2 + 5n + 7 steps is O(n^2).

Common orders, from fastest to slowest:

Notation Name Example
O(1) Constant Array access by index, hash lookup
O(log n) Logarithmic Binary search
O(n) Linear Linear search, one loop
O(n log n) Linearithmic Merge sort
O(n^2) Polynomial Bubble sort, nested loops
O(2^n) Exponential Naive recursive Fibonacci, brute-force subsets
O(n!) Factorial Trying every ordering (travelling salesman brute force)

Doubling the input roughly doubles the time for O(n), quadruples it for O(n^2), and squares the work for O(2^n). With n = 50, an O(2^n) algorithm needs over a quadrillion steps, which is why exponential algorithms are only usable for tiny inputs.

Finding complexity from code

  • A single loop through n items: O(n).
  • A loop inside a loop, both up to n: O(n^2).
  • A loop that halves the problem each time: O(log n).
  • A statement with no loop: O(1).
FOR i <- 1 TO n          // runs n times
  FOR j <- 1 TO n        // runs n times for each i
    OUTPUT i * j
  NEXT j
NEXT i                   // total n * n = O(n^2)

Time and space

Time complexity counts the steps; space complexity counts the extra memory. They often trade off: merge sort is fast but uses extra memory, while bubble sort uses none but is slow. A hash table uses more memory to give faster lookups.

Why it matters

Complexity shows whether a solution will still work when data grows from a hundred to a million items. A problem with no known polynomial-time solution (for example brute-force route planning) may require heuristics, which give a good answer, not necessarily the best one. Sometimes a program is judged by best, average and worst case: quicksort averages O(n log n) but its worst case is O(n^2).

Check your understanding

What is the Big-O of a single loop over n items?

  • O(1)
  • O(n)
  • O(n^2)
  • O(log n)

Answer: O(n). The work grows in proportion to n.

Simplify 4n^2 + 10n + 3.

  • O(n)
  • O(n^2)
  • O(4n^2)
  • O(10n)

Answer: O(n^2). Drop constants and lower-order terms.

Which is the most efficient for large n?

  • O(n^2)
  • O(2^n)
  • O(n log n)
  • O(n!)

Answer: O(n log n). The others grow far faster.

What does space complexity measure?

  • Extra memory an algorithm uses
  • Screen size
  • Time taken
  • Number of users

Answer: Extra memory an algorithm uses. It is often traded against time.

PreviousNext