An appropriate description of an object or an algorithm readily admits a combinatorial description of its size or complexity. This is especially important for computer scientists because we want to analyze the complexity of the programs we develop. We measure the complexity of a program by expected amount of resources that it consumes as a function of the size of its input. By resources, we typically mean either the time the program takes to execute—its time complexity—or the amount of memory the program consumes while executing—its space complexity. In CSC 207, you’ll explore program complexity as it relates to the fundamental data structures of computer science. In this reading, we’ll approach the topic of program complexity as an exercise in applied counting.

Critical Operations

The true amount of resources that a program takes to execute depends on many factors, e.g., applications running at the same time, the underlying operating system or hardware, most of which we cannot hope to easily capture with a mathematical function. We therefore approximate the complexity of a function by choosing a measure that implies the amount of resources a program uses while executing but is ultimately independent of these particular details. Usually, this measure is the number of critical operations that a program executes. The actual operations that we count are highly dependent on the program under consideration; we ultimately want to pick a minimal number of operations that is manageable to analyze but also accurately reflects the behavior of the program. In particular, when we analyze time complexity, we can use our critical operation(s) as the “unit” of time that the program takes to execute.

For example, consider the standard racket implementation of the factorial function:

(define factorial
  (lambda (n))
    (if (= n 0)
        1
        (* n (factorial (- n 1)))))

A natural candidate for critical operations to count, here, are multiplications. Multiplications are the core behavior of the factorial computation. Furthermore, we intuitively believe they are the most common operation that occurs in factorial. Because of this, we can have confidence that the number of multiplications is a good approximation of the total time that factorial takes to run.

However, this is not the only operation we might consider. For example, we might consider equality comparisons, i.e., how many times we evaluate (= n 0) during the evaluation of factorial. Choosing equalities versus multiplications will lead in slightly different counts of total operations. In CSC 207, you will learn about Big-O notation that will allow you to conclude that these differences don’t matter. For now, we’ll simply note that both are reasonable choices as critical operations without further proof.

An Aside: Imperative Racket Code and C

Much of the Racket you have written in CSC 151 and this course has been in a pure, functional style. That is, we have written functions like mathematical functions that take inputs and produce outputs without any side-effects such as changing the value of variables in our program. However, Racket provides such facilities to program in a more conventional style. For example, suppose that we wish to print a sequence of strings to the console. The following function accomplishes this with the (begin ...) special form:

(define display-string
  (lambda ()
    (begin (display "!")
           (display "#")
           (display "$")
           (display "%"))))

Note that this function does not return a string. It instead prints the strings "!", "#", "$", and "%" to the console, one after the other. Printing is another example of a side-effect, similar to variable mutation. (begin ...) allows us to sequence these side-effects so that they happen one after the other.

If want to perform repetitive behavior in a sequential, effect-ful manner, Racket also provides a standard library function (for-each action lst). for-each takes each element found in list lst in left-to-right order and calls the single-argument function action on that element. For example, the following Racket function prints out the numbers from 0 to n-1. (Recall that (range n) returns the list '(0 1 ... (- n 1)).)

(define display-range
  (lambda (n)
    (for-each (lambda (i) (display i))
              (range n))))

Writing imperative code in Racket is relatively onerous, but it is natural in other, more conventional languages. If you are familiar with C, the analogous definitions of these functions are:

void display_string() {
    printf("!");
    printf("#");
    printf("$");
    printf("%");
}

void display_range(int n) {
    for (int i = 0; i < n; i++) {
        printf("%d", i);
    }
}

Counting Operations

Once we’ve identified our critical operations, we can now go about the business of counting them in our programs. In the absence of branching constructs, i.e., straight line code, this is straightforward: simply count all the occurrences of the operation in the code! For example, if we are counting calls to display as our critical operations, then display-string above clearly calls display four times.

When we sequence a series of actions, e.g., with begin, we can take the union of their resulting operations, i.e., add them up. For example, in the following begin block:

(begin
  (display-string)
  (display-string)
  (display-string))

We call display-string three times, each of which calls display three times, so there are \(3 + 3 + 3 = 9\) calls made overall.

Things get more interesting when we move from straight-line code to code that involves branching. We’ll first focus on loops. Let’s attempt to count the number of times display-range calls display.

(define display-range
  (lambda (n)
    (for-each (lambda (i) (display i))
              (range n))))

Recall that for-each call the given function over every element of the input list. Here, the function in question calls display once, and the number of elements is n since (range n) produces the list (0 ... (- n 1)). Thus, (display-range n) calls display \(1 ⋅ n = n\) times. We can express as a (mathematical) function of \(n\), \(f(n) = n\) represents the number of times display is called as a function of the input n.

Another tool that we can use to capture this quantity in a way that’s more indicative of the structure of the code is summation notation. We recognize that the loop performs a set of repeated, sequential actions that, as per our previous discussion, can be combined with addition. Thus, we really have:

\[ f(n) = \underbrace{1 + 1 + ⋯ + 1}_{n}. \]

Summation notation allows to express this repeated addition concisely:

\[ \sum_{i = 0}^{n-1} 1. \]

We can think of a summation as the direct encoding of a for-loop. It is composed of three parts:

• Below the \(\Sigma\) (upper-case sigma), an initializer for a bound variable that may appear in the body of the summation.
• Above the \(\Sigma\), an (inclusive) upper-bound on the bound variable. This is the final value of the bound variable of the summation.
• To the right of the \(\Sigma\), the body of the summation which describes each summand. The body appears as a summand once for each value the bound variable takes on.

In this particular case, the bound variable is \(i\) and it ranges from \(0\) to \(n - 1\), inclusive. For each of these values of \(i\), the summand \(1\) appears in the overall sum. In other words:

\[ \sum_{i = 0}^{n-1} 1 = \underbrace{1 + ⋯ + 1}_{n}. \]

Note that the range from \(0\) to \(n - 1\), inclusive, includes \(n\) numbers. Contrary to computer programming however, mathematicians tend to use 1-indexing rather than 0-indexing as we normally do with our loops. This would be the more colloquial way to write this summation in math terms.

\[ \sum_{i = 1}^{n} 1 = \underbrace{1 + ⋯ + 1}_{n}. \]

In this particular, the two summations are equivalent because the body of the summation doesn’t reference \(i\). But if it does, then the meaning of the summation changes slightly. For example, consider these two summations that mention the bound variable in their bodies:

\[\begin{gather} \sum_{i = 0}^{n-1} i = 0 + 1 + ⋯ + (n-1) \\ \sum_{i=1}^{n} i = 1 + 2 + ⋯ + n = \frac{n(n+1)}{2} \end{gather}\]

The change of lower- and upper-bounds of the variable resulted in a shift of the summands by one! Note that we can fix this by adjusting our usage of the variable in the body of the summand. For example, if we wanted to fix the \(1\)–\(n\) summation so that it behaved like the \(0\)–\(n - 1\) summation.

\[ \sum_{i = 1}^{n} (i-1) = (1-1) + (2-1) + ⋯ + (n-1) = 0 + 1 + ⋯ + (n-1). \]