Loading...
A growth class describes a model of work as input size increases. Compare the same case and implementation, include preparation costs and explain why an algorithm fits the actual dataset.
What you'll be able to do
Input size might mean the number of list entries, vertices, edges or characters; state which quantity n represents. Time analysis counts relevant operations under a model, rather than directly measuring seconds on every machine. Big O supplies an asymptotic upper growth bound; a useful answer identifies the intended tight class where known instead of treating it as an exact timing equation.
Constant work does not grow with n, logarithmic work grows slowly, linear work tracks n, and polynomial work includes n² and other fixed powers. Exponential growth such as 2ⁿ can quickly make exhaustive exploration impractical. Constants and hardware still affect practical times, especially on small datasets; growth analysis and measurement answer related but different questions.
A linear search can find the first item in constant time, while an absent item can require checking the whole list. Binary search has a constant-time successful best case and logarithmic worst-case comparisons, assuming suitable sorted indexed data. Sorting an unsorted list to answer one query may cost more than a direct linear search.
The table describes particular standard implementations. Optimised bubble sort can stop after a no-swap pass; the ordinary always-recursive merge sort still performs splitting and merging on already sorted data. Quicksort’s pivot choices affect balance. Average-case claims require a model of input distribution; “average” does not mean simply halfway between the best and worst time.
Auxiliary space is extra space beyond the input storage under a stated convention. In-place insertion sort uses constant auxiliary storage. Array-based merge sort commonly needs linear temporary storage; an in-place quicksort can still need recursion-stack space. Count return structures separately when the problem requires a new output rather than modifying an existing collection.
For many repeated queries on stable data, sorting once or building an index can be worthwhile. For a streaming source, severe memory limit or frequent updates, a different trade-off may suit the task. Recommend an algorithm by linking preconditions, case behaviour, memory and preparation to the scenario. Neither “fastest Big O” nor “fewest lines” alone captures all requirements.
| Algorithm / stated variant | Best time | Typical average time | Worst time |
|---|---|---|---|
| Linear search | O(1) | O(n) | O(n) |
| Binary search, sorted indexed data | O(1) | O(log n) | O(log n) |
| Insertion sort | O(n) | O(n²) | O(n²) |
| Bubble sort with early exit | O(n) | O(n²) | O(n²) |
| Standard recursive array merge sort | O(n log n) | O(n log n) | O(n log n) |
| Quicksort, ordinary two-way partition | O(n log n) | O(n log n) | O(n²) |
| n | 1 | log₂ n | n | n² | 2ⁿ |
|---|---|---|---|---|---|
| 8 | 1 | 3 | 8 | 64 | 256 |
| 16 | 1 | 4 | 16 | 256 | 65,536 |
| 32 | 1 | 5 | 32 | 1,024 | 4,294,967,296 |
Attempt the task before opening its worked response. Record each change of state, explain the rule used, and check the result against the original requirements. Code examples labelled Python 3 use that language’s conventions; pseudocode states its own assumptions.
Common mistakes to avoid
Key takeaways
Test yourself
Answer a few questions, then review anything you missed.
Start with the quiz above to check the key ideas. You can also choose another topic from the practice library.