Skip to content
Tutorials Center
My learning

Topics

Lesson 7 of 225 · Analyzing Algorithms

Analyzing Loops and Code

Learn to read code and work out its time complexity. Single loops, nested loops, halving loops, dependent loops and the hidden cost of Python built-ins.

Big O notation gives you a vocabulary for growth: O(1), O(log n), O(n), O(n²) and friends. This lesson is about the skill that goes with it: looking at a piece of code and deciding which of those labels it earns. You don't need a formula for this. You need to count how many times the busiest line runs, as a function of the input size n, and then keep only the fastest-growing term.

The best way to learn is to make the machine count for you. In this lesson every example carries a step counter, a plain integer that goes up each time the interesting line runs. Counting steps is more reliable than timing code, because the count never changes from one computer to the next, while a stopwatch does.

The counting method

To analyze a function, follow four steps:

  1. Decide what n is. It is usually the length of a list or string, or the value of a number.
  2. Pick the dominant operation, the line that runs most often (a comparison, an addition, an assignment).
  3. Count how many times it runs, in terms of n.
  4. Drop constants and lower-order terms: 3n + 7 becomes O(n), and n² + 5n becomes O(n²).

Lines that run a fixed number of times, no matter how big the input is, cost O(1) each. They never decide the answer unless the whole function has nothing else.

A single loop is O(n)

A loop that visits every element once does work proportional to the length of the list. Doubling the list doubles the steps.

Python One loop, one step per item

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The step count equals n every time, so the function is O(n). A loop that does a constant amount of extra work per item, such as three additions instead of one, is still O(n): the constant 3 disappears in Big O.

TEXT
n = 5
 index:  0   1   2   3   4
         |   |   |   |   |
 step:   1   2   3   4   5     -> 5 steps = n steps

Two loops placed one after the other are sequential. Their costs add, and the bigger one wins: O(n) followed by O(n) is O(2n), which is O(n); O(n) followed by O(n²) is O(n² + n), which is O(n²).

Nested loops multiply

When one loop runs inside another, the inner loop starts fresh for every pass of the outer one. The costs multiply.

Python Nested loops and the triangle

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The first function runs n × n = n² steps. The second is a dependent loop: the inner loop's length depends on the outer variable. When i = 0 the inner loop runs n − 1 times, when i = 1 it runs n − 2 times, and so on down to 0. The total is

TEXT
(n-1) + (n-2) + ... + 1 + 0  =  n(n-1) / 2

You can check this against the output: for n = 100 the formula gives 100 × 99 / 2 = 4950. Since n(n−1)/2 = n²/2 − n/2, we drop the constant factor 1/2 and the lower term, and the triangle is still O(n²). This is exactly the pattern of comparing every pair of items once, which you will meet again in two pointers and in brute-force solutions throughout the course.

A handy shortcut: three nested loops that each run to n give O(n³); k nested loops give O(n^k). But always check the bounds. Nested loops are only n × n when both ranges grow with the input.

Loops that halve or double: O(log n)

Not every loop moves by one. If the loop variable is multiplied or divided on every pass, the number of passes is the number of times you can double (or halve) before hitting the limit, and that is a logarithm.

Python Halving and doubling

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For a million items the loop runs only about twenty times. That is why O(log n) is so precious: searching a sorted list of a million items by repeatedly halving it takes around twenty comparisons, as you will see in binary search.

TEXT
n = 16
16 -> 8 -> 4 -> 2 -> 1        4 halvings  =  log2(16)

The base of the logarithm does not matter in Big O, because log₂ n and log₁₀ n differ only by a constant factor. We write O(log n) and move on.

Be careful when a loop looks like it halves but does not. while i < n: i += 2 adds 2, so it runs n/2 times, which is O(n). Only multiplication and division by a constant (i *= 2, n //= 3) give logarithmic loops.

A loop that runs while i * i <= n stops around √n, so it is O(√n). You will see it in primality tests (see number theory).

A loop inside a log loop

Combine the shapes by multiplying: an outer loop that runs n times with an inner loop that halves costs O(n log n). This is the signature cost of efficient sorting such as merge sort.

Python n times log n

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For powers of two the count equals n × log₂ n exactly (n.bit_length() − 1 is log₂ n here, hence the little expression in the last column).

Different variables: O(n + m) and O(n × m)

Sometimes a function receives two inputs of unrelated size. Don't call both n. If you loop over one list and then over the other, the cost is O(n + m). If you loop over one list for every item of the other, it is O(n × m).

Python Two inputs, two variables

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Writing the answer as O(n²) when the lists have different lengths is a common mistake. Keep separate letters until you know the sizes are tied together.

Hidden loops in Python built-ins

Python hides loops inside single-line operations. A line that looks like one step can be a full pass over the data, and forgetting this is the biggest source of accidental O(n²) code.

Operation Typical cost Why
lst[i], len(lst), lst.append(x) O(1) direct indexing; append is amortized (see amortized analysis)
x in lst, lst.index(x), lst.count(x) O(n) scans the list item by item
lst.insert(0, x), lst.pop(0) O(n) every later item shifts one place
lst.pop() O(1) removes from the end
lst[a:b] O(b − a) copies that many references
sorted(lst), lst.sort() O(n log n) comparison sort
x in my_set, key in my_dict O(1) on average hashing
s + t for strings O(len(s) + len(t)) builds a brand new string

You can prove an O(n) claim with a counter. This class counts the comparisons that in performs:

Python Counting what x in list really does

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Finding the first item takes one comparison, the middle item takes 500, the last takes 1000, and a missing item also takes 1000. The cost depends on where the answer is, a theme we explore in best, worst and average case. In the worst case, in is O(n).

Now watch what that does inside a loop. This function removes duplicates, and it looks harmless:

Python A hidden loop makes this quadratic

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The for loop is O(n) and the not in seen check inside is O(n), so unique_slow is O(n²) when most items are distinct. Swapping the list for a set turns the check into O(1) on average and the whole function into O(n). This one change, "use a hash set for membership", is among the most common optimizations in interview problems.

Common mistakes

  • Counting lines instead of loops. Ten statements inside a loop are still one pass.
  • Assuming nested means n². If the inner loop is bounded by a constant (say range(3)), the total is O(3n) = O(n).
  • Forgetting the cost of slicing and copying. lst[1:] inside a recursive function copies the list on every call.
  • Ignoring in on lists. It is a loop.
  • Using one letter for two inputs. Say O(n + m) when you mean it.
  • Confusing the value of n with its size. A loop for i in range(n) over an integer is O(n) in the value of n, but the number itself has only about log n digits. For beginners the value is what matters, but keep this in mind for number theory.

Check your understanding

Quick check · 5 questions

of 5 answered You scored / 5 · perfect!

  1. 1. What is the time complexity of a loop for i in range(n) containing another loop for j in range(5)?

    The inner loop always runs exactly 5 times, which is a constant. The total is 5n steps, and constants are dropped, leaving O(n).
  2. 2. How many times does while n > 1: n //= 2 run for n = 1024?

    1024 is 2 to the power 10, so 10 halvings bring it down to 1. The loop is O(log n).
  3. 3. An outer loop runs i from 0 to n-1, and the inner loop runs j from i+1 to n-1. What is the total step count, in Big O?

    The inner loop runs n-1, n-2, ..., 0 times. The sum is n(n-1)/2, which is proportional to n², so O(n²).
  4. 4. Why is if x not in some_list: inside a loop over n items usually a problem?

    Membership in a list is a linear scan. Doing it n times in a row gives O(n²). A set makes each check O(1) on average.
  5. 5. A function loops over list a (length n) and then separately over list b (length m). Which is the right complexity?

    Sequential loops add. Running one after the other costs n + m steps, so the answer is O(n + m).

Summary

  • To find the time complexity, count the dominant operation as a function of n, then drop constants and lower-order terms.
  • One pass is O(n); nested passes multiply; sequential passes add, and the bigger one wins.
  • A dependent inner loop such as range(i + 1, n) sums to n(n−1)/2, which is still O(n²).
  • Loops that multiply or divide the variable by a constant take O(log n) passes; adding a constant is still linear.
  • Use different letters for independent inputs: O(n + m) or O(n × m).
  • Built-ins hide loops. in on a list, insert(0, x), slicing and string concatenation are all O(n). Sets and dicts give O(1) average lookups.
  • A step counter is the most reliable way to check your analysis.

Next: Space Complexity