Time Complexity and Big-O Notation for Beginners

By QuizMaster Learn Team, 2026-10-27

When you write a program, it is not enough that it gives the right answer; it should also stay fast when the input grows. Time complexity describes how the running time of an algorithm increases with the size of the input, and Big-O notation is the standard way to write it.

Common complexities

• O(1), constant time: the work does not depend on the input size, for example reading one element of an array by its index.
• O(log n), logarithmic: the problem is cut down quickly, as in binary search or Euclid’s algorithm for the greatest common divisor.
• O(n), linear: you look at every element once, such as finding the largest number in a list.
• O(n log n): typical of efficient sorting algorithms such as merge sort.
• O(n²), quadratic: usually two nested loops, for example comparing every pair of items.
• O(n³), cubic: three nested loops, like the standard method for multiplying two matrices.

Why constants are ignored

Big-O describes growth, not exact time. An algorithm that does 3n steps and one that does 100n steps are both O(n), because doubling the input doubles the work in both cases. What matters is the shape of the curve.

An example: Strassen’s algorithm

The ordinary method for multiplying two n × n matrices takes about n³ steps. Strassen’s divide and conquer algorithm reduces the number of recursive multiplications from eight to seven, which lowers the complexity to about O(n^2.81). That is a real improvement for very large matrices.

How to practise

Look at each loop in a program and ask how many times it runs compared with the input size. Then test yourself with the Algorithms and Data Structures quizzes, where every explanation shows the reasoning step by step.