Python algorithm complexity

Compare linear work with quadratic work by counting operations.

Python

def work(n):
    linear = 0
    quadratic = 0
    for _ in range(n):
        linear += 1
    for _ in range(n):
        for _ in range(n):
            quadratic += 1
    return linear, quadratic

print(work(3))
print(work(6))
assert work(0) == (0, 0)

Output

(3, 9)
(6, 36)

Explanation

Asymptotic complexity describes how resource use grows with input size. It is not an exact wall-clock prediction: hardware, constants, and the operations being counted still matter.

One loop over n values makes n visits. Two nested full loops make n*n visits. This example counts iterations explicitly instead of using noisy timing measurements.

Explore the dry run

Guided walkthroughReady

1def work(n):

2 linear = 0

3 quadratic = 0

4 for _ in range(n):

5 linear += 1

6 for _ in range(n):

7 for _ in range(n):

8 quadratic += 1

9 return linear, quadratic

11print(work(3))

12print(work(6))

13assert work(0) == (0, 0)

Follow the example

Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.

View the complete dry-run table

Prepared trace of the published program. Some rows group repeated iterations.
What happens	State after step	Output so far
For n=3, the single loop increments three times.	`linear = 3`	—
Three outer iterations each run three inner iterations.	`quadratic = 9`	—
Print the two counts.	`quadratic = 9`	(3, 9)
For n=6, the single loop makes 6 visits and nested loops make 36.	`linear = 6, quadratic = 36`	(3, 9)
Doubling n doubles linear work and quadruples quadratic work.	`linear = 6, quadratic = 36`	(3, 9) (6, 36)

Cost and common mistakes

The combined function is Θ(n²) time and O(1) counters under the unit-cost arithmetic model.

Big O is an upper-bound notation; use the tight bound when describing these loops.
Nested loops are not always quadratic: inspect their actual bounds.

Try it yourself

Predict work(10).

Reveal answer and reasoning

It returns (10, 100). Increasing to 20 gives (20, 400).

Python algorithm complexity

Explanation

Follow the example

Cost and common mistakes

Try it yourself

Further reading