DSA Time Complexity

How it works

The example counts comparisons made by a scan that does not stop early. Doubling the number of items doubles that count. Real elapsed time also includes interpreter effects, allocations and hardware behaviour, so these counts are not a prediction of milliseconds. Big O describes an upper growth bound; say whether the statement is worst-case, average-case, amortized or about a particular input family.

Run the code

Select Try in playground to load this complete source into the existing Python editor. It does not run automatically; choose Run when ready. These examples use only the Python standard library and small fictional inputs. They do not need database services, extra packages or personal files.

For local work, save the complete source as growth.py and run python growth.py. The local review uses Python 3.12.14; the browser uses the existing Pyodide 0.27.7 runtime. Keep inputs small, respect explicit table/tour budgets and account for recursion limits before increasing a fixture’s size.

Example

def scan_count(values, target):
    comparisons = 0
    for value in values:
        comparisons += 1
        if value == target:
            return comparisons
    return comparisons

print(scan_count([2, 4, 6, 8], 99))
print(scan_count(list(range(8)), 99))

Expected result

4
8

The absent target forces every element to be checked. A first-position match would be a different case, not evidence that a scan has constant worst-case cost. Keep the input pattern visible when comparing algorithms or interpreting a benchmark.

Time, space and assumptions

This scan is O(n) worst-case and O(1) best-case when the first item matches. It stores O(1) auxiliary state; the input list itself is not counted as newly allocated workspace.