Python · Course navigation

Python algorithm complexity

Compare linear work with quadratic work by counting operations.

On this page

Before you start

Loops and function return values.

Compare linear work with quadratic work by counting operations.
Predict the sample output and explain the state changes.
Complete the practice task and check the boundary cases.

The concept

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.

Code example

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)

Example details

Follow the code

Open the walkthrough to inspect the example one step at a time.

Show guided walkthrough

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)

Behind the scenes

How Python processes this code

Python runs this source through its interpreter. It creates objects for values and resolves names as each statement runs.

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).