How fast is your code?

Introduction

Two programs can give the same answer while one takes a thousand times longer. Complexity describes how the work a program does grows as its input grows. The visualizer's step counter makes this easy to see.

A program that works on your ten test items can be useless on a million real ones. Complexity lets you predict that before it happens, and it is one of the main things that separates a programmer from a computer scientist.

How it works

Searching one by one

nums = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
target = 91
checks = 0
for x in nums:
    checks += 1
    if x == target:
        break
print("found after", checks, "checks")

Linear search checks every item in order. The target 91 is the last of 10 items, so it takes 10 checks. Note the total in the step label ("Step … of 36") as well. With 1000 items, the worst case would be 1000 checks: the work grows in step with the input. We write this as O(n).

How work grows

for n in [10, 100, 1000]:
    print(n, "items:", n, "steps for one loop,", n * n, "for a loop inside a loop")

A loop inside a loop does n × n steps. That is fine for 10 items (100 steps) but heavy for 1000 (a million steps).

Syntax

# O(1)        nums[5]
# O(log n)    binary search
# O(n)        for x in nums: ...
# O(n log n)  sorted(nums)
# O(n^2)      a loop inside a loop

Example

nums = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
target = 91
low, high = 0, len(nums) - 1
checks = 0
while low <= high:
    checks += 1
    mid = (low + high) // 2
    if nums[mid] == target:
        break
    elif nums[mid] < target:
        low = mid + 1
    else:
        high = mid - 1
print("found after", checks, "checks")

Binary search only works on a sorted list, but it is far faster. Each round it looks at the middle item and throws away the half that cannot contain the target. The calculation box shows the middle position being worked out: (low + high) // 2 → (0 + 9) // 2 → 4.

It finds 91 after 4 checks instead of 10. Every check halves what is left, so 1000 items need about 10 checks and a million about 20. We write this as O(log n).

Line by line

1. low and high mark the part of the list still to be searched.
2. Each round increases checks and finds the middle position.
3. If the middle item is the target, the loop ends.
4. If it is too small, the search continues to the right of it, so low moves past it.
5. Otherwise, high moves to the left of it, and half the list is gone either way.

Expected result

found after 4 checks

In the real world

Search engines and databases handle billions of records because they use the logarithmic methods shown here. A careless O(n²) step is a classic cause of pages that are fine in testing and then time out on real data.

Common mistakes

• Using binary search on an unsorted list. It returns wrong answers; sort first or search linearly.
• Thinking only of small inputs. Code that is instant for 10 items can be unusably slow for 100000.
• Forgetting that x in my_list is a hidden loop (O(n)), while x in my_set is close to O(1).

Best practices

• Work out how large your data can really get.
• Use a set or dictionary for repeated lookups.
• Make it work first, then measure, and only then improve what is slow.

Summary

Complexity describes how work grows with input. Binary search is O(log n) on sorted data, a single loop is O(n), and nested loops are O(n²). Choosing the right approach matters more and more as data grows.

Practice

Change target in both search examples to 2, then to 56. Count the checks each time, and explain why linear search wins for 2.

Mark lesson complete