The Link class implements linked lists in Python. Each Link instance has a first attribute (which stores the first value of the linked list) and a rest attribute (which points to the rest of the linked list).

class Link:
    empty = ()

    def __init__(self, first, rest=empty):
        assert rest is Link.empty or isinstance(rest, Link)
        self.first = first
        self.rest = rest

    def __repr__(self):
        if self.rest is not Link.empty:
            rest_repr = ', ' + repr(self.rest)
        else:
            rest_repr = ''
        return 'Link(' + repr(self.first) + rest_repr + ')'

    def __str__(self):
        string = '<'
        while self.rest is not Link.empty:
            string += str(self.first) + ' '
            self = self.rest
        return string + str(self.first) + '>'

An empty linked list is represented as Link.empty, and a non-empty linked list is represented as a Link instance.

The rest attribute of a Link instance is always another linked list! When Link instances are linked via their rest attributes, a sequence is formed.

To check if a linked list is empty, compare it to the class attribute Link.empty.

Throughout this class, we have mainly focused on correctness — whether a program produces the correct output. However, computer scientists are also interested in creating efficient solutions to problems. One way to quantify efficiency is to determine how a function's runtime changes as its input changes. In this class, we measure a function's runtime by the number of operations it performs.

A function f(n) has...

• constant runtime if the runtime of f does not depend on n. Its runtime is Θ(1).
• logarithmic runtime if the runtime of f is proportional to log(n). Its runtime is Θ(log(n)).
• linear runtime if the runtime of f is proportional to n. Its runtime is Θ(n).
• quadratic runtime if the runtime of f is proportional to n^2. Its runtime is Θ(n^2).
• exponential runtime if the runtime of f is proportional to b^n, for some constant b. Its runtime is Θ(b^n).

Example 1: It takes a single multiplication operation to compute square(1), and it takes a single multiplication operation to compute square(100). In general, calling square(n) results in a constant number of operations that does not vary according to n. We say square has a runtime complexity of Θ(1).

Example 2: It takes a single multiplication operation to compute factorial(1), and it takes 100 multiplication operations to compute factorial(100). As n increases, the runtime of factorial increases linearly. We say factorial has a runtime complexity of Θ(n).

Example 3: Consider the following function:

def bar(n):
    for a in range(n):
        for b in range(n):
            print(a,b)

Evaulating bar(1) results in a single print call, while evalulating bar(100) results in 10,000 print calls. As n increases, the runtime of bar increases quadratically. We say bar has a runtime complexity of Θ(n^2).

Example 4: Consider the following function:

def rec(n):
    if n == 0:
        return 1
    else:
        return rec(n - 1) + rec(n - 1)

Evaluating rec(1) results in a single addition operation. Evaluating rec(4) results in 2^4 - 1 = 15 addition operations, as shown by the diagram below.

During the evaulation of rec(4), there are two calls to rec(3), four calls to rec(2), eight calls to rec(1), and 16 calls to rec(0).

So we have eight instances of rec(0) + rec(0), four instances of rec(1) + rec(1), two instances of rec(2) + rec(2), and a single instance of rec(3) + rec(3), for a total of 1 + 2 + 4 + 8 = 15 addition operations.

As n increases, the runtime of rec increases exponentially. In particular, the runtime of rec approximately doubles when we increase n by 1. We say rec has a runtime complexity of Θ(2^n).

Tips for finding the order of growth of a function's runtime:

• If the function is recursive, determine the number of recursive calls and the runtime of each recursive call.
• If the function is iterative, determine the number of inner loops and the runtime of each loop.
• Ignore coefficients. A function that performs n operations and a function that performs 100 * n operations are both linear.
• Choose the largest order of growth. If the first part of a function has a linear runtime and the second part has a quadratic runtime, the overall function has a quadratic runtime.
• In this course, we only consider constant, logarithmic, linear, quadratic, and exponential runtimes.