Consider building a reversed copy of a string s of length n. Because strings are immutable, the running time is:

reverse = ''
for i in range(n):
    reverse = s[i] + reverse

Appending n items one at a time to an initially empty Python list takes total time proportional to:

What is the order of growth of x after this code runs?

x = 0
for i in range(n):
    for j in range(n):
        for k in range(n):
            x += 1

What is the order of growth of the running time of this function?

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

You run a doubling test on two Section 4.2 sorting functions. For f the successive running-time ratios settle near 4; for g they settle near 2. Which pairing is correct?

For which input does insertion sort run in LINEAR time in n?

Using the text's memory model, an array (Python list) holding 1000 int objects (each in the normal 64-bit range) uses about:

A program's worst-case running time is O(n²). According to the text, which statement is TRUE?

For n a power of 2, mergesort is linearithmic because:

In the worst case, the number of compares binary search uses on a sorted array of n keys has order of growth: