What is the time complexity of a loop nested inside another, each running n times?
- Inner loop: n steps per outer iteration.
- Outer: n iterations.
- n × n = O(n²).
Answer O(n²)
A-level Computer Science revision · Data structures and algorithms
Big O notation describes how an algorithm's time or space grows with input size n, keeping the dominant term. Constant O(1), logarithmic O(log n), linear O(n), polynomial O(n²), exponential O(2ⁿ). Better complexity matters most for large inputs.
Watch out An O(n²) algorithm can be faster than O(n) for very small n; Big O describes growth.
What is the time complexity of a loop nested inside another, each running n times?
Answer O(n²)
What is the time complexity of binary search?
An algorithm's time is proportional to n². It takes 4 seconds for n = 1000. Roughly how long would it take for n = 2000, in seconds?
Which complexity grows fastest as n increases?
A-level Computer Science Pro, OCR H446
£119 once
Price rises to £199 on 1 January. Save £80 by joining before then.
At least 12 months of access
No VAT is charged.