9.5 Analyzing Algorithm Running Time

Let us consider a very similar function to print_integers from the beginning of the chapter:

def print_items(lst: list) -> None:
    for item in lst:
        print(item)

Here, print_items takes a list as input instead, and so \(n\) is equivalent to len(lst). For the remainder of this course, we will assume input size for a list is always its length, unless something else is specified. How can we use our asymptotic notation to help us analyze the running time of this algorithm? Earlier, we said that the call to print took 1 “basic operation”, but is that true? The answer is, it doesn’t matter. By using asymptotic notation, we no longer need to worry about the constants involved, and so don’t need to worry about whether a single call to print counts as one or ten “basic operations”.

Just as switching from measuring real time to counting “basic operations” allows us to ignore the computing environment in which the program runs, switching from an exact step count to asymptotic notation allows us to ignore machine- and programming language-dependent constants involved in the execution of the code. Having ignored all these external factors, our analysis will concentrate on how the size of the input influences the running time of a program, where we measure running time just using asymptotic notation, and not exact expressions.

Warning: the “size” of the input to a program can mean different things depending on the type of input, or even depending on the program itself. Whenever you perform a running time analysis, be sure to clearly state how you are measuring and representing input size.

Because constants don’t matter, we will use a very coarse measure of “basic operation” to make our analysis as simple as possible. For our purposes, a basic operation (or step) is any block of code whose running time does not depend on the size of the input.To belabour the point a little, this depends on how we define input size. For integers, we usually will assume they have a fixed size in memory (e.g., 32 bits), which is why arithmetic operations take constant time. But of course if we allow numbers to grow infinitely, this is no longer true, and performing arithmetic operations will no longer take constant time.

This includes all primitive language operations like most assignment statements, arithmetic calculations, and list and string indexing. The one major statement type which does not fit in this category is a function call—the running time of such statements depends on how long that particular function takes to run. We’ll revisit this in more detail later.

The running time function

The running time of print_items depends only on the size of the input list, and not the contents of the list. That is, we expect that print_items takes the same amount of time on every list of length \(100\). We can make this a little more clear by introducing one piece of notation that will come in handy for the rest of the chapter.

For example, \(\cI_{print\_items, 100}\) is simply the set of all lists of length 100. \(\cI_{print\_items, 0}\) is the set containing just one input: the empty list.

We can restate our observation about print_items in terms of these sets: for all \(n \in \N\), every element of \(\cI_{print\_items, n}\) has the same runtime when passed to print_items.

Our first technique for performing this runtime analysis follows four steps:

1. Identify the blocks of code which can be counted as a single basic operation, because they don’t depend on the input size.
2. Identify any loops in the code, which cause basic operations to repeat. You’ll need to figure out how many times those loops run, based on the size of the input. Be exact when counting loop iterations.
3. Use your observations from the previous two steps to come up with an expression for the number of basic operations used in this algorithm—i.e., find an exact expression for \(RT_{func}(n)\).
4. Use the properties of asymptotic notation to find an elementary function \(f\) such that \(RT_{func} \in \Theta(f(n))\).

Because Theta expressions depend only on the fastest-growing term in a sum, and ignores constants, we don’t even need an exact, “correct” expression for the number of basic operations. This allows us to be rough with our analysis, but still get the correct Theta expression.

def print_items(lst: list) -> None:
    for item in lst:
        print(item)

Here is a second example, which has a similar structure to our first example, but also features slightly more code, using the familiar loop accumulator pattern.

def my_sum(numbers: list[int]) -> int:
    sum_so_far = 0

    for number in numbers:
        sum_so_far = sum_so_far + number

    return sum_so_far

Nested loops

It is quite possible to have nested loops in a function body, and analyze the running time in the same fashion. The simplest method of tackling such functions is to count the number of repeated basic operations in a loop starting with the innermost loop and working your way out.

def print_sums(lst: list) -> None:
    for item1 in lst:
        for item2 in lst:
            print(item1 + item2)

A common misconception about nested loops!

Students often make the mistake that the number of nested loops should always be the exponent of \(n\) in the Big-O expression.E.g., two levels of nested loops always becomes \(\Theta(n^2)\). However, things are not that simple, and in particular, not every loop takes \(n\) iterations.

def f(lst: list[int]) -> None:
    for item in lst:
        for i in range(0, 10):
            print(item + i)

def all_pairs(lst: list[int]) -> None:
    for i in range(0, len(lst)):
        for j in range(0, i):
            print(lst[i] + lst[j])

def combined(lst: list[int]) -> None:
    # Loop 1
    for item in lst:
        for i in range(10):
            print(item + i)

    # Loop 2
    for item1 in lst:
        for item2 in lst:
            print(item1 + item2)