9.6 Analyzing Comprehensions and While Loops

In the previous section, we began our study of algorithm running time analysis by looking at functions that are implemented using for loops. We chose for loops as a starting point because they make explicit the repeated statements that occur when we execute a function body, while also being relatively straightforward to analyze because of their predicable iteration patterns.

In this section, we’ll extend what we learned about for loops to two different kinds of Python code: comprehension expressions and while loop. We’ll see how all three obey similar patterns when it comes to repeating code, but while loops offer both more flexibility and more complexity in what they can do.

Comprehensions

Consider the following function:

def square_all(numbers: list[int]) -> list[int]:
    """Return a new list containing the squares of the given numbers."""
    return [x ** 2 for x in numbers]

Importantly, the fact that a comprehension is creating a new collection (in our above example, a list) does not count as additional time when analysing the cost of a comprehension. This is true for all three of list, set, and dictionary comprehensions, and so the same analysis would hold in the above function if we had used a set or dictionary comprehension instead.

While loops

Analysing the running time of code involving while loops follows the same principle using for loops: we calculate the sum of the different loop iterations, either using multiplication (when the iteration running time is constant) or a summation (when the iterations have different running times). There is one subtle twist, though: a while loop requires that we write statements to initialize the loop variable(s) before the loop, and update the loop variable(s) inside the loop body. We must be careful to count the cost of these statements as well, just like we did for statements involving loop accumulators in the previous section.

To keep things simple, our first example is a simple rewriting of an earlier example using a while loop instead of a for loop.

def my_sum_v2(numbers: list[int]) -> int:
    """Return the sum of the given numbers."""
    sum_so_far = 0
    i = 0

    while i < len(numbers):
        sum_so_far = sum_so_far + numbers[i]
        i = i + 1

    return sum_so_far

Now, the previous example was a little contrived because we could have implemented the same function more simply using a for loop. Here is another example, which uses a while loop to compute powers of two to act as indexes into a list.

def my_sum_powers_of_two(numbers: list[int]) -> int:
    """Return the sum of the given numbers whose indexes are powers of 2.

    That is, return numbers[1] + numbers[2] + numbers[4] + numbers[8] + ...
    """
    sum_so_far = 0
    i = 1

    while i < len(numbers):
        sum_so_far = sum_so_far + numbers[i]
        i = i * 2

    return sum_so_far

A trickier example

It turns out that the extreme flexibility of while loops can make analysing their running time much more subtle than it might appear. Our next example considers a standard loop, with a twist in how the loop variable changes at each iteration.

def twisty(n: int) -> int:
    """Return the number of iterations it takes for this special loop to stop
    for the given n.
    """
    iterations_so_far = 0
    x = n
    while x > 1:
        if x % 2 == 0:
            x = x / 2
        else:
            x = 2 * x - 2
        iterations_so_far = iterations_so_far + 1

    return iterations_so_far

Even though the individual lines of code in this example are simple, they combine to form a pretty complex situation. The challenge with analyzing the runtime of this function is that, unlike previous examples, here the loop variable x does not always get closer to the loop stopping condition; sometimes it does (when divided by two), and sometimes it increases!

The key insight into analyzing the runtime of this function is that we don’t just need to look at what happens after a single loop iteration, but instead perform a more sophisticated analysis based on multiple iterations. As preparation, try tracing twisty on inputs \(7\), \(9\), and \(11\). More concretely, we’ll prove the following claim.

Now let’s see how take this claim and use it to formally analyse the running time of twisty.

Something funny happened at the end of the above analysis: we did not actually compute the exact number of steps the function twisty takes, only an upper bound on the number of steps (signalled by our use of the phrase “at most”). This means that we were only able to conclude a Big-O bound, and not a Theta bound, on the running time of this function: its running time is at most \(\cO(n)\), but we don’t know whether this bound is tight.

In fact, it isn’t! It is possible to prove something pretty remarkable about what happens to the variable x after three iterations of the twisty loop.

It is a good exercise to prove this claim Hint: you can use the same approach as the previous claim, but consider remainders when you divide by 8 instead of 4. and then use this claim to conduct a more detailed running time analysis of twisty. When you do so, you should be able to show that the running time of twisty is both \(\cO(\log n)\) and \(\Omega(\log n)\), and hence conclude that its running time is actually \(\Theta(\log n)\), not just \(\cO(n)\)!