Time complexity
Describe how an algorithm's work grows as input size increases.
What you will learn
- Recognise constant, linear and quadratic growth.
- State assumptions when assigning a complexity.
Count growing operations
Time complexity describes the growth of work with input size n, rather than a stopwatch time on one computer. If an algorithm processes each item once using a bounded amount of work per item, its running time grows linearly.
Big-O gives an asymptotic upper bound. In common classroom comparisons, O(n) describes linear growth and O(n²) quadratic growth, but you should also state whether you are discussing the worst case, average case or another case.
Look inside loops
One loop over n elements is linear if its body takes constant time. Two nested loops each covering n elements can require n² body executions. Two separate loops over n elements require about 2n operations, which still has linear growth.
A loop that repeatedly halves a search range can have logarithmic growth, provided its other work does not dominate. Do not classify complexity from the number of visible loops alone.
Worked example
An algorithm scans a list of n values once to find the largest. Explain its worst-case time complexity.
Show the worked solution
- Each value is examined once.
- Each examination requires a bounded comparison and possible update.
- The number of operations grows in direct proportion to n.
Answer O(n)
Common mistakes
- Two consecutive linear scans are O(n), not O(n²).
- An expensive operation inside a loop can change its complexity.
What can you explain now?
Two nested loops each run n times and the inner body takes constant time. What is the growth?
Compare with the explanation
O(n²)
The inner body executes n times for each of n outer iterations.
After trying it yourself, choose your next review. This is your self-assessment.
Your review choice appears on Today. Sign in to sync it across devices.