Reading the cost of loops

Complexity analysis Junior Python 3.13+ Reviewed By Best Latest Apps

Predict the output

What does this print?

Python 3.13
n = 10
count = 0
for outer in range(n):
    for _ in range(outer):
        count += 1
print(count, n * (n - 1) // 2)

Options

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A 45 45

Right: 0 + 1 + … + 9 = 45, which is n(n - 1)/2.

Half of n² is still quadratic, so a dependent inner loop does not change the Big O class.

Why not the others?
  • B 100 45. The inner loop runs i times, not n times.
  • C 55 45. range(i) stops before i, so the largest inner count is 9.

30-second answer

Count how many times the innermost statement runs. Independent nested loops multiply: n × m. A dependent inner loop such as for j in range(i) runs 0 + 1 + … + (n - 1) = n(n - 1)/2 times, which is still O(n²). Loops one after another add, so O(n) + O(n²) is O(n²).

Practise saying it · 45 s. No recording, just a timer

Explain how to read the cost of nested loops.

Say your answer out loud, then check which of these points you covered:

  • Count the innermost line
  • Dependent loops sum to n²/2
  • Hidden O(n) operations

Deep dive

A while loop is analysed the same way: how many times can its condition stay true?

Hidden loops count: x in list, slicing, list.index and sum(list) are each O(n).

Two pointers or a sliding window inside a for loop can still be O(n) if each pointer only moves forward.

Common mistakes

  • Calling a dependent loop O(n log n) because the inner loop 'gets shorter'.
  • Missing the O(n) cost of in on a list inside a loop.

Senior take & follow-ups

Write the sum out loud (0 + 1 + … + n - 1). It shows the count is real, not guessed.

Follow-up questions

Think of your answer first, then open the hint.

  1. What if the inner loop steps by i + 1 each time, from i up to n?

    Show hint

    About n/1 + n/2 + … + n/n steps, the harmonic sum, which is O(n log n).

  2. How do you analyse a loop that doubles?

    Show hint

    It runs log₂ n times.

Similar on Backend: OFFSET vs keyset pagination Paging through a table with OFFSET re-reads every skipped row, so fetching all pages costs a sum like 0 + k + 2k + …, the same quadratic shape as a dependent loop. Keyset pagination removes it.

What each operation costs: Bubble Sort · Merge Sort · Binary Search

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.