Time complexity

Different algorithms can solve the same problem, but they may take very different amounts of time. The time complexity of an algorithm describes how the time it takes grows as the amount of data grows. For small data the difference hardly matters; for huge data sets it matters a great deal.

A simple way to estimate it is to look at the loops:

• No loop: the algorithm takes the same time whatever the data size: constant time.
• One loop running from 1 to n: the time grows in step with n: linear time.
• A loop inside a loop (a nested loop): for each of n steps, another n steps run, so the time grows as n²: quadratic time.

If an algorithm has both a single loop and a nested loop, the nested loop decides: its complexity is quadratic, since n² grows much faster than n.

Bubble, selection and insertion sort all use nested loops, so they all take quadratic time (n²). That is fine for small lists, but for very large ones, faster sorting methods are used.