Algorithm Complexity and Big-O
How to estimate an algorithm's speed before running it: Big-O notation and the 10⁸ operations per second rule.
A correct answer is only half of a contest problem. The other half is fitting into the time limit, usually 1–2 seconds. That is why the first thing a competitive programmer learns is estimating an algorithm's speed BEFORE writing the code.
Speed is measured as the number of operations as a function of the input size n and written in Big-O notation:
• O(1) — constant: the answer comes from a formula;
• O(log n) — halving the problem: binary search;
• O(n) — a single pass over the data;
• O(n log n) — sorting;
• O(n²) — two nested loops;
• O(2ⁿ) — exhaustive search over subsets.
The key practical rule: a computer performs on the order of 10⁸ simple operations per second. Plug your n into the complexity formula — and you know whether the solution will pass.
How many operations does each algorithm need? Enter n, for example: 100000
Try entering 1000, then 100000, then 1000000000 — and compare the lines with the 10⁸ rule. You can see why an O(n²) solution at n = 10⁵ no longer passes (10¹⁰ operations — a hundred seconds), while O(n log n) passes easily.
Feel the difference live: the program below sums the numbers from 1 to n in two ways — with an O(n) loop and with an O(1) formula. Enter 1000000000 (a billion) and watch the running time: the loop takes noticeable time, the formula is instant. The answers match.
Enter 1000000000 and compare: the loop visibly thinks, the formula is instant
How to assess your own code:
• nested loops multiply: a loop over n inside a loop over n is O(n²);
• sequential blocks add up, and the largest wins: O(n) + O(n log n) = O(n log n);
• constants are dropped: 5n operations is still O(n).
Task: estimate the complexity of three fragments — (1) finding the maximum in one pass; (2) checking all pairs of elements; (3) a loop where n is halved each time. Answers: O(n), O(n²), O(log n).
Solve the attached problem "Sum of Array Elements" — the classic single O(n) pass — and mark the lesson as completed.