Study Guide: Orders of Growth

Instructions

This is a study guide about orders of growth with links to past lectures, assignments, and handouts, as well as additional practice problems to assist you in learning the concepts.

Assignments

Important: For solutions to these assignments once they have been released, see the main website

Handouts

Lectures

Readings

Guides

Time complexity

The time complexity of an algorithm is an approximation of the time required to run a computer program as the input size increases. We typically express time complexity using either Big-Theta or Big-O notation, which ignores the constant factor needed for fixed operations and focuses instead on the operations that increase proportional to input size. We then classify orders of growth based on the type of function in the Big-Theta notation. For example, a program with a Θ(n) complexity generally requires double the time if the input doubles, and a program with Θ(2n) complexity has a linear order of growth.

This table summarizes the most common orders of growth:

Order Time complexity Example
Constant Θ(1) Indexing an item in a list
Logarithmic Θ(lg N) Repeatedly halving a number
Linear Θ(n) Summing a list
Quadratic Θ(n^2) Summing each pair of numbers in a list
Exponential Θ(2^n) Visiting each node in a binary tree

Constant time

When an algorithm runs in constant time, it means that it always takes a fixed number of steps, no matter how large the input size increases.

As an example, consider accessing the first element of a list:

first_post = posts[0]

Even if the list grows to be a million items long, that operation will always require a single step.

We can visualize that relationship as a table:

List size Steps
1 1
10 1
100 1
1000 1

We can also visualize it as a graph:

Constant graph

A constant run time is ideal, but is typically not possible for algorithms that process multiple pieces of data.

Logarithmic time

When an algorithm runs in logarithmic time, it increases proportionally to the logarithm of the input size.

The binary search algorithm is an example of an algorithm that runs in logarithmic time.

Here's the pseudocode:

def search_list(nums, target_num):
    """ Returns the index of TARGET_NUM in sorted list NUMS or -1 if not found.
    >>> search_list([1, 2, 3, 4], 3)
    2
    >>> search_list([14, 23, 37, 48, 59], 23)
    1
    >>> search_list([14, 23, 37, 48, 59], 47)
    -1
    """
    min_index = 1
    max_index = len(nums)
    while min_index <= max_index:
        middle_index = (min_index + max_index) // 2
        if target_num == nums[middle_index]:
            return middle_index
        elif target_num > nums[middle_index]:
            min_index = middle_index + 1
        else:
            max_index = middle_index - 1
    return -1

The algorithm uses a loop to look at multiple items in the list, but crucially, it does not look at every item in the list. Specifically, it looks at lg2(n) items, where n is the number of items in the list.

We can visualize that relationship in a table:

List size Steps
1 1
10 4
100 7
1000 10

We can also see that as a graph:

Logarithmic graph

The number of steps is definitely increasing as input size increases, but at a very slow rate.

Linear time

When an algorithm grows in linear time, its number of steps increases in direct proportion to the input size.

The aptly-named linear search algorithm runs in linear time.

The code shows its simplicity compared to binary search:

def search_list(nums, target_num):
    """ Returns the index of TARGET_NUM in an unsorted list NUMS or -1 if not found.
    >>> search_list([3, 2, 1, 4], 3)
    2
    >>> search_list([14, 59, 99, 23, 37, 22], 23)
    3
    >>> search_list([14, 59, 99, 23, 37, 22], 47)
    -1
    """
    index = 1
    while index < len(nums):
        if nums[index] == target_num:
            return index
        index += 1
    return -1

This time, the loop looks at every item in the list. This exhaustive search is necessary to search for items in an unsorted list, since there's no way to narrow down where a particular item might be. This algorithm will always require at least as many steps as items in the list.

We can see that in table form:

List size Steps
1 1
10 10
100 100
1000 1000

Or as a graph:

Linear graph

Quadratic time

When an algorithm grows in quadratic time, its steps increase in proportion to the input size squared.

Several list sorting algorithms run in quadratic time, like selection sort. That algorithm starts from the front of the list, then keeps finding the next smallest value in the list and swapping it with the current value.

Here's pseudocode for selection sort:

def linear_sort(nums):
    """Performs an in-place sorting of NUMS.
    >>> l = [2, 3, 1, 4]
    >>> linear_sort(l)
    >>> l
    [1, 2, 3, 4]
    """
    i = 0
    while i < len(nums):
        min_index = i
        j = i + 1
        # Find next smallest value
        while j < len(nums):
            if nums[j] < nums[min_index]:
                min_index = j
            j += 1
        # Swap if new minimum found
        if min_index != i:
            nums[i], nums[min_index] = nums[min_index], nums[i]
        i += 1

The important thing to notice about the algorithm is the nested loop: it loops through each items in the list, and loops again through the remaining items for each of those items. In this case, the algorithm ends up looking at 1/2 * (n^2 - n) values, where n is the number of items in the list.

This table shows how many items it'd examine for lists of increasing sizes:

List size Steps
1 1
10 45
100 4950
1000 499500

Here's what that looks like in graph form:

Quadratic graph

Both the table and the graph show that the number of steps for this algorithm increases at a much faster rate than the previous ones.

Exponential time

When an algorithm grows in superpolynomial time, its number of steps increases faster than a polynomial function of the input size.

An algorithm often requires superpolynomial time when it must look at every permutation of values. For example, consider an algorithm that generates all possible numerical passwords for a given password length.

For a password length of 2, it generates 100 passwords:

00 01 02 03 04 05 06 07 08 09
10 11 12 13 14 15 16 17 18 19
20 21 22 23 24 25 26 27 28 29
30 31 32 33 34 35 36 37 38 39
40 41 42 43 44 45 46 47 48 49
50 51 52 53 54 55 56 57 58 59
60 61 62 63 64 65 66 67 68 69
70 71 72 73 74 75 76 77 78 79
80 81 82 83 84 85 86 87 88 89
90 91 92 93 94 95 96 97 98 99

That algorithm requires at least 10^2 steps, since there are 10 possibilities for each digit (0-9) and it must try out every possibility for each of the 2 digits.

For any given password length of n, the algorithm requires 10^n steps. That run time increases incredibly quickly, since each additional digit requires 10 times the number of steps.

This table shows how fast that grows for just the first 5 digits:

Digits Steps
1 10
2 100
3 1000
4 10000
5 100000

Here's what that looks like as a graph:

Exponential graph

All together now

Now that we've seen examples of possible run times for algorithms, let's compare them on a graph:

All graphs overlaid

That graph makes it even more clear that there's a definite difference in these run times, especially as input size increases. Since modern computer programs increasingly deal with large data sets (like from millions of users or sensors), the run time efficiency matters quite a bit.

Practice Problems

Easy

Q1: Bonk

Describe, in Big O or Big Theta notation, the order of growth of the function below.

def bonk(n):
    sum = 0
    while n >= 2:
        sum += n
        n = n / 2
    return sum

ϴ(log(n)). As we increase the value of n, the amount of time needed to evaluate a call to bonk scales logarithmically. Let's use the number of iterations of our while loop to illustrate an example. When n = 1, our loop iterates 0 times. When n = 2, our loop iterates 1 time. When n = 4, we have 2 iterations. And when n = 8, a call to bonk(8) results in 3 iterations of this while loop. As the value of the input scales by a factor of 2, the number of iterations increases by 1. This helps indicate that this function has logarithmic runtime.

Medium

Q2: Pow

Write the following function so it runs in ϴ(log k) time.

Hint: this can be done using a procedure called repeated squaring.

def pow(n,k):
    """Computes n^k.

    >>> pow(2, 3)
    8
    >>> pow(4, 2)
    16
    >>> a = pow(2, 100000000) # make sure you have log time
    """
"*** YOUR CODE HERE ***"
if k == 1: return n if k % 2 == 0: return pow(n*n,k//2) else: return n * pow(n*n, k//2)

Q3: Boom

What is the order of growth in time for the following function boom? Use big-ϴ notation.

def boom(n):
    sum = 0
    a, b = 1, 1
    while a <= n*n:
        while b <= n*n:
            sum += (a*b)
            b += 1
        b = 0
        a += 1
    return sum

ϴ(n4)

We can come to this answer by noticing that either b = 0 or b = 1 when we start the while b <= n * n loop, and we increase b by 1 every time, so this loop takes about n * n time. Thus, the body of the while a <= n * n loop takes n * n time, and therefore the whole function takes n * n * n * n time, or ϴ(n4)