LESSON 141 · DEEPER PYTHON30 min

Understand Python Algorithmic Complexity with Measured Inputs

Measure how comparison counts grow for linear and binary search on increasing sorted inputs.

Before you start: Loops · Functions · Find Insertion Points with bisect

Example check: Worked and guided code samples are checked against CPython 3.13. Practice uses Pyodide 0.29.5 (Python 3.13) in your browser. How we check lessons

WATCH

Video lesson: Understand Python Algorithmic Complexity with Measured Inputs

The preview is stored on this site. YouTube loads only when you press Play. Watch on YouTube

Jump to a chapter

Read the video transcript

Select a timestamp to watch that moment on YouTube.

00:00
A list membership test is written on one line. Does that mean Python performs one comparison? We will search for the last item in lists of eight and one hundred values, then make the hidden work visible. The outputs are True in both cases, but correctness alone does not tell us how effort scales. This lesson compares two algorithms under a controlled pattern: linear search and binary search over sorted integers. We will count actual inspected values rather than rely on one wall-clock number from one computer. That lets us explain the mechanism behind the growth. Before running anything, predict how many values a linear scan must inspect when the
00:40
target is last. Big O describes how resource use grows as input size grows; it is not a stopwatch prediction for one tiny run. A list membership expression can look like one line while scanning many elements. For a target at the end of a list of one hundred items, linear search may compare one hundred values. Binary search can inspect far fewer values, but only when the data is sorted and random access is available. We will count actual comparisons so the demonstration is stable across machines instead of claiming that one timing sample proves an asymptotic law.
01:20
The first run prints True for both list sizes and labels each expression as one source line. That label is the flawed reasoning we want to expose. The expression can hide a loop inside Python's implementation. You cannot infer time complexity by counting lines of source code, just as a single function call can process a million records. The two membership expressions also have different input sizes, so their equal boolean result says nothing about equal work. Instead of benchmarking them immediately, we will reconstruct the comparison process in a short loop. That loop is not meant to replace the built-in membership operation in
02:01
production; it is a measuring instrument for learning. The broken explanation prints True for membership in a list of eight and a list of one hundred. It treats each expression as one operation because the source code is one line. The output reveals correctness but says nothing about work inside the search. Diagnose the hidden scan with an explicit loop that increments a counter for each inspected value. Keep the target at the end so every linear step is visible. Avoid declaring a winner from wall-clock time alone: startup, caching, and input size can dominate tiny measurements. The diagnostic loop increments a counter before each equality check and breaks when
02:43
it finds the target. With the target at the end, the eight- element case inspects eight items and the hundred-element case inspects one hundred. Change the target to the first item and both searches need only one comparison; that is a different case. Complexity descriptions summarize how resource use grows under stated conditions, often the worst case, rather than promising one fixed count for every input. Our chosen last-element pattern makes the linear growth easy to see. Next we will keep the same sorted range and compare a strategy that discards much more than one candidate at a time.
03:23
A binary search starts in the middle of sorted data and discards half of the remaining candidates after each comparison. Count each middle-element inspection, move the low bound right when the middle is too small, and move the high bound left when it is too large. The target at the last position in a range of eight takes four comparisons; the same target pattern in a range of one hundred takes seven. This is a concrete growth contrast, not a universal benchmark. Binary search on unsorted input can give a wrong result, so sorted order is an explicit precondition. Binary search checks the middle item. If it is smaller than the target in a sorted list, every item to its left can be
04:06
discarded; the low bound moves right. If it is larger, the high bound moves left. The fixed function counts these middle inspections and returns both counts. For eight values with the target last, it reports eight linear comparisons and four binary comparisons. The difference is a property of the algorithm and chosen input, not a claim that binary search is always faster after every setup cost. If the data is unsorted, moving the bounds this way is invalid. Sorted order is part of the function's explanation, not a footnote. The fixed code is deliberately explicit rather than clever.
04:46
Its first loop shows exactly where each linear comparison occurs. The second loop maintains inclusive low and high bounds. It counts once for each inspected midpoint, then either stops on equality or removes a half of the current candidate interval. Using range keeps the example compact but still supports indexed access. The function returns measured counts for a specified target position, so its tests do not depend on CPU speed, browser load, or timer resolution. This is a model for reasoning about work; production code can use bisect when the same sorted-search task is needed without the educational counters.
05:28
Finally we compare sizes one, eight, and one hundred. Both algorithms inspect one item in the one-element case. As the last position moves farther away, linear steps grow with the input length, while binary steps rise much more slowly. We also reject size zero because there is no last item to search for. In a real application, you would consider how the data became sorted, how many searches are performed, memory use, and measurements on representative inputs. A list, set, database index, or preprocessed array changes the tradeoff. Complete the article task by returning counts, then use the quiz to explain why a
06:09
single timing result cannot establish a general complexity class. The verification run checks sizes one, eight, and one hundred. Linear comparisons grow with the chosen worst-case position; binary comparisons grow much more slowly. The function rejects nonpositive size instead of inventing a range with no last element. A set membership check has different average behavior and memory cost, but we are not measuring that implementation here. For a real optimization, measure the operation that matters with representative data, keep correctness tests separate, and consider setup costs such as sorting.
06:49
The learning task asks you to return comparison counts so its result remains deterministic.

THE IDEA

Understand the concept

Big O describes how resource use grows as input size grows; it is not a stopwatch prediction for one tiny run. A list membership expression can look like one line while scanning many elements. For a target at the end of a list of one hundred items, linear search may compare one hundred values. Binary search can inspect far fewer values, but only when the data is sorted and random access is available. We will count actual comparisons so the demonstration is stable across machines instead of claiming that one timing sample proves an asymptotic law.

The broken explanation prints True for membership in a list of eight and a list of one hundred. It treats each expression as one operation because the source code is one line. The output reveals correctness but says nothing about work inside the search. Diagnose the hidden scan with an explicit loop that increments a counter for each inspected value. Keep the target at the end so every linear step is visible. Avoid declaring a winner from wall-clock time alone: startup, caching, and input size can dominate tiny measurements.

A binary search starts in the middle of sorted data and discards half of the remaining candidates after each comparison. Count each middle-element inspection, move the low bound right when the middle is too small, and move the high bound left when it is too large. The target at the last position in a range of eight takes four comparisons; the same target pattern in a range of one hundred takes seven. This is a concrete growth contrast, not a universal benchmark. Binary search on unsorted input can give a wrong result, so sorted order is an explicit precondition.

The verification run checks sizes one, eight, and one hundred. Linear comparisons grow with the chosen worst-case position; binary comparisons grow much more slowly. The function rejects nonpositive size instead of inventing a range with no last element. A set membership check has different average behavior and memory cost, but we are not measuring that implementation here. For a real optimization, measure the operation that matters with representative data, keep correctness tests separate, and consider setup costs such as sorting. The learning task asks you to return comparison counts so its result remains deterministic.

Big O describes scaling
One line can hide many comparisons
Binary search requires sorted data
Count operations separately from timing noise

WORKED EXAMPLES

See it step by step

Read the code, predict the output, then compare it with the result.

01. Count a last-item linear scan

PYTHON

values = list(range(8)); target = 7
steps = 0
for value in values:
    steps += 1
    if value == target: break
print(steps)

EXPECTED OUTPUT

The final item requires eight inspections in this eight-element list.

02. Count middle inspections

PYTHON

values = list(range(8)); target = 7
low, high, steps = 0, len(values)-1, 0
while low <= high:
    mid = (low+high)//2; steps += 1
    if values[mid] == target: break
    if values[mid] < target: low = mid+1
    else: high = mid-1
print(steps)

EXPECTED OUTPUT

Every middle comparison discards a region of sorted candidates.

03. Compare measured counts

PYTHON

print('linear:', 8, 100)
print('binary:', 4, 7)

EXPECTED OUTPUT

linear: 8 100
binary: 4 7

These exact counts describe the selected last-item scenarios, not every possible target.

GO DEEPER

A closer look

Follow the reasoning, inspect each result, then try the suggested changes in the console below.

01 / 03

Expose hidden comparisons

Big O describes how resource use grows as input size grows; it is not a stopwatch prediction for one tiny run. A list membership expression can look like one line while scanning many elements. For a target at the end of a list of one hundred items, linear search may compare one hundred values. Binary search can inspect far fewer values, but only when the data is sorted and random access is available. We will count actual comparisons so the demonstration is stable across machines instead of claiming that one timing sample proves an asymptotic law.

Run the loop and count every inspection. Move the target to the first position and observe that linear search can also finish quickly. Complexity statements usually distinguish worst, average, and best cases.

PYTHON

values = list(range(8)); target = 7
steps = 0
for value in values:
    steps += 1
    if value == target: break
print(steps)

EXPECTED OUTPUT

Follow the reasoning

Move the target position.
Count inspected elements.

02 / 03

Use sorted order to halve work

The broken explanation prints True for membership in a list of eight and a list of one hundred. It treats each expression as one operation because the source code is one line. The output reveals correctness but says nothing about work inside the search. Diagnose the hidden scan with an explicit loop that increments a counter for each inspected value. Keep the target at the end so every linear step is visible. Avoid declaring a winner from wall-clock time alone: startup, caching, and input size can dominate tiny measurements.

Trace low, mid, and high for each step. The algorithm can discard half only because a smaller middle value implies the target lies to its right in sorted data. Try the same loop on scrambled values and see why the precondition matters.

PYTHON

values = list(range(8)); target = 7
low, high, steps = 0, len(values)-1, 0
while low <= high:
    mid = (low+high)//2; steps += 1
    if values[mid] == target: break
    if values[mid] < target: low = mid+1
    else: high = mid-1
print(steps)

EXPECTED OUTPUT

Follow the reasoning

Trace low and high.
State the sorted-input requirement.

03 / 03

Interpret measured growth

A binary search starts in the middle of sorted data and discards half of the remaining candidates after each comparison. Count each middle-element inspection, move the low bound right when the middle is too small, and move the high bound left when it is too large. The target at the last position in a range of eight takes four comparisons; the same target pattern in a range of one hundred takes seven. This is a concrete growth contrast, not a universal benchmark. Binary search on unsorted input can give a wrong result, so sorted order is an explicit precondition.

Compare a list of eight with a list of one hundred, but keep the target pattern consistent. A timing chart would need repeated measurements and setup-cost context; the exact comparison counts already show the growth mechanism for this example.

PYTHON

print('linear:', 8, 100)
print('binary:', 4, 7)

EXPECTED OUTPUT

linear: 8 100
binary: 4 7

Follow the reasoning

Compare multiple sizes.
Do not infer a universal runtime from one sample.

HANDS-ON

Try it in Python

Edit the example and run it. Python starts in your browser the first time you click Run.

Python console

Ready to run

def comparison_counts(size):
    values = list(range(size))
    target = values[-1]
    print(target in values)
    return (1, 1)

print(comparison_counts(8))

Need input()? Add one value per line

Input lines

Ctrl / ⌘ + Enter to run

OUTPUT

Your output appears here.

Your turnReturn (linear_steps, binary_steps) for finding the last value in sorted range(size). Count actual inspected elements and reject size below one with ValueError. For size 8 return (8, 4).

Need a hint?

Increment once per comparison in each loop; binary search moves low or high around the middle index.

Complete the task and select Check task to verify your code.

DEBUG BETTER

Typical mistakes

Everyone meets these errors. See what causes them and how to fix them.

Counting lines instead of work

COMMON MISTAKE

return (1, 1) because each search is one expression

FIX

increment a counter for every inspected element

What happens: The model hides a scan over many list elements.
Separate a source-code statement from the operations it performs.

Binary search on unsorted data

COMMON MISTAKE

discard half of an arbitrary list

FIX

state and preserve sorted-input precondition

What happens: The target may be discarded despite being present.
The direction of each bound change depends on ordering.

Browse this lesson’s problem fixes

VERIFY THE STORY

Sources and further reading

Python bisect documentation