One Pass Over the Data
O(n) means linear time: the work grows in step with the input. Twice the elements, twice the steps.
In Python, linear time usually looks like one for loop over a list or a dictionary. Every algorithm that must at least look at every element — summing, counting, searching an unsorted list — cannot be faster than O(n).
Linear is a good complexity. Millions of elements are no problem for one pass.
Linear Search
When the list is not sorted, the only way to find a value is to check the elements one by one, from the start. That is a linear search.
In the worst case — the value is last, or not there at all — the loop visits all n elements. That worst case is what O(n) describes.
Find a value and its position
The loop checks "one", "two", "three" before it reaches "four" — 4 steps for a match at index 3. break stops the loop as soon as the value is found.
Output: complete Python program
words = ["one", "two", "three", "four", "five"]
steps = 0
for i, w in enumerate(words):
steps += 1
if w == "four":
print("found at index", i, "after", steps, "steps")
break
Visiting Every Element
Many everyday tasks are one pass over the whole list: add all values, keep the biggest one seen so far, count the elements that pass a test. Each element is touched exactly once, so all of them are O(n).
Doing two or three of these passes in a row is still linear — O(2n) and O(3n) collapse to O(n).
Sum all elements
The loop adds every element to total. 8 elements, 8 additions — the classic one-pass shape.
Output: complete Python program
nums = [3, 1, 4, 1, 5, 9, 2, 6]
total = 0
for n in nums:
total += n
print("sum of", len(nums), "elements:", total)
Find the biggest value
biggest starts as the first element; every other element that is bigger replaces it. After one pass the biggest value, 9, remains.
Output: complete Python program
nums = [3, 1, 4, 1, 5, 9, 2, 6]
biggest = nums[0]
for n in nums[1:]:
if n > biggest:
biggest = n
print("biggest value:", biggest)
Count the matches
The loop tests every word with len(w) > 3 and counts the hits. Three words are longer than 3 letters.
Output: complete Python program
words = ["one", "two", "three", "four", "five"]
count = 0
for w in words:
if len(w) > 3:
count += 1
print(count, "words are longer than 3 letters")