Complexity describes how work grows as input grows. Start by tracing a real algorithm, choosing what to count and separating its best and worst cases before attaching a complexity label.
Define the operation you are counting
For linear search, comparisons against the target are a useful count. Finding the target in the first position requires one comparison, while an absent target requires checking the whole list. The counting model is a simplified explanation of growth, not an exact prediction of milliseconds on every computer.
Keep assumptions visible
Binary search uses sorted data and narrows a remaining interval. A different data structure or unsorted input changes what is possible. Include the cost of preparing the data if sorting is part of the actual task. A logarithmic lookup does not make an entire workflow logarithmic when an earlier step dominates the work.
Measure space as well as time
An algorithm can trade additional memory for faster repeated operations. Describe extra space separately from the input itself and state whether a data structure is copied. Then test empty input, duplicates, boundary positions and missing values. These cases often expose incorrect reasoning that a typical example misses.
Worked example
The example searches five values and counts each comparison. Looking for 7 reaches the fourth position, so the output is 4. In the absent-target case, the count becomes five. The loop is a concrete starting point for an O(n) worst-case explanation.
values = [2, 4, 6, 7, 9]
comparisons = 0
for value in values:
comparisons += 1
if value == 7:
break
print(comparisons)
Expected output
4Check your understanding
Try each question before opening its explanation. These are free practice prompts; they do not use game chances.
Does O(n) mean exactly n milliseconds?
No. It describes an asymptotic bound on growth under stated assumptions. Constants, hardware and input distribution influence observed runtime.
Can one algorithm have different best and worst cases?
Yes. Linear search may succeed immediately or inspect every position. State the case you mean instead of presenting one count as the only possible behaviour.
How many comparisons occur if the target is absent here?
Five comparisons occur because every value is checked. If the list were empty, the loop would run zero times and the count would remain zero.
Sources and further reading
These original examples explain foundational concepts. Use the official references for complete, current details and version-specific behaviour.
About this guide: AI-assisted educational content with original examples and linked primary references. Found an issue? Tell us what to improve.