09 A simplistic Introduction to Algorithmic Complexity (Chapter 9)

The exact step count of the factorial loop

Here is the factorial function with a counter added to it. The counter lines are not part of the function being measured: they are the measuring instrument, and each one records the price of the line above or below it.

def fact_steps(n):
    """Assumes n is an int and n >= 0.
    Returns n factorial and the number of steps the plain version uses.
    """
    answer = 1
    steps = 1
    while n >= 1:
        steps = steps + 1
        answer = answer * n
        steps = steps + 2
        n = n - 1
        steps = steps + 2
    steps = steps + 1
    return answer, steps


for size in [1, 3, 10, 1000]:
    value, used = fact_steps(size)
    print('n =', size, 'steps =', used, 'and 5n+2 =', 5 * size + 2)

Sample Run:

n = 1 steps = 7 and 5n+2 = 7
n = 3 steps = 17 and 5n+2 = 17
n = 10 steps = 52 and 5n+2 = 52
n = 1000 steps = 5002 and 5n+2 = 5002

Find the step count as a formula in n, and check it against the run.

Why the same algorithm gives two different counts, and why that is fine

A classmate counts the same factorial loop and gets 4n + 2 rather than 5n + 2. Her reason: she treats answer = answer * n as one step, because on the page it is one operation being written into one name.

Decide who is right, and say what the disagreement costs.

Simplifying 1000 + x + 2 x squared, and seeing the terms take over

This function does three separate pieces of work: a loop of fixed length, a loop of length x, and a pair of nested loops over x with two additions in the body. It prints the running count after each piece, so the three terms are visible separately.

def f(x):
    """Assumes x is an int > 0. Returns the number of additions done."""
    ans = 0
    for i in range(1000):
        ans = ans + 1
    print('after the first loop', ans)
    for i in range(x):
        ans = ans + 1
    print('after the second loop', ans)
    for i in range(x):
        for j in range(x):
            ans = ans + 1
            ans = ans + 1
    print('after the nested loops', ans)
    return ans


f(10)
print()
f(1000)

Sample Run:

after the first loop 1000
after the second loop 1010
after the nested loops 1210

after the first loop 1000
after the second loop 2000
after the nested loops 2002000

Find the count as a formula in x, then the class.

Showing that 8n + 400 is O of n, with the two constants written down

A function has been counted and its step count is 8n plus 400. Show that this is O of n by naming a multiplier and a size, and then show that the same count is not O of the constant function 1.

The three cases of a scan that stops at the first negative number

This function walks a list and returns as soon as it meets a negative number. The counter records how many positions it read, so the four runs below show four different costs for the same function on lists of the same length.

def first_negative(L):
    """Assumes L is a list of numbers.
    Returns the position of the first negative number, or -1 if there is
    none, together with the number of positions looked at.
    """
    looked = 0
    for i in range(len(L)):
        looked = looked + 1
        if L[i] < 0:
            return i, looked
    return -1, looked


print(first_negative([-4, 7, 7, 7, 7]))
print(first_negative([7, 7, -4, 7, 7]))
print(first_negative([7, 7, 7, 7, -4]))
print(first_negative([7, 7, 7, 7, 7]))

Sample Run:

(0, 1)
(2, 3)
(4, 5)
(-1, 5)

Give the best, worst and average case as formulas in n, and the class of each.

A loop whose best case is not its first pass

This function is given a list that is already in increasing order, and it uses that to stop early when the wanted value cannot be ahead. The counter shows what it cost on three lists of the same length.

def in_sorted(L, e):
    """Assumes L is a list of ints in increasing order.
    Returns whether e is in L, and how many positions were
    read.
    """
    read = 0
    for i in range(len(L)):
        read = read + 1
        if L[i] == e:
            return True, read
        if L[i] > e:
            return False, read
    return False, read


L = [10, 20, 30, 40, 50]
print(in_sorted(L, 10))
print(in_sorted(L, 5))
print(in_sorted(L, 25))
print(in_sorted(L, 99))

Sample Run:

(True, 1)
(False, 1)
(False, 3)
(False, 5)

Say what the best case is, what the worst case is, and whether knowing the list is sorted changed the class.

The halving loop, counted, and why 1000 takes only 9 passes

This is the loop shape behind every logarithmic program in the course. It divides its counter instead of decreasing it, and the run shows how few passes that takes even on large values.

def halvings(n):
    """Assumes n is an int >= 1.
    Returns how many times n can be halved with // before it reaches 1.
    """
    count = 0
    while n > 1:
        n = n // 2
        count = count + 1
    return count


for size in [1, 8, 1000, 1000000]:
    print(size, 'needs', halvings(size), 'halvings')

Sample Run:

1 needs 0 halvings
8 needs 3 halvings
1000 needs 9 halvings
1000000 needs 19 halvings

Explain the four counts, and give the class of the loop in terms of the value of n.

Building an n log n loop and an exponential loop from bare parts

Two of the six classes have no single loop that produces them, so here they are built. The first nests a halving loop inside a pass over the list. The second has one loop whose number of passes is itself a power of two.

def log_linear(L):
    """Assumes L is a list. Returns the number of inner passes."""
    passes = 0
    for i in range(len(L)):
        m = len(L)
        while m > 1:
            m = m // 2
            passes = passes + 1
    return passes


def exponential(n):
    """Assumes n is an int >= 0.
    Returns how many on and off patterns n switches have.
    """
    rows = 0
    for code in range(2 ** n):
        rows = rows + 1
    return rows


for size in [8, 16, 1024]:
    print(size, log_linear(list(range(size))))
for n in [3, 10, 20]:
    print('n =', n, 'rows =', exponential(n))

Sample Run:

8 24
16 64
1024 10240
n = 3 rows = 8
n = 10 rows = 1024
n = 20 rows = 1048576

Give the class of each function and check it against the run.

A function with a loop, then a nested loop, then a halving loop

Three pieces of work in one function, one after another. The middle piece is nested and the last piece divides its counter. Find the class.

def report(L):
    """Assumes L is a list of ints with at least one item.
    Returns the largest item, the number of equal pairs, and the
    number of halvings the length survives.
    """
    biggest = L[0]
    for x in L:
        if x > biggest:
            biggest = x
    pairs = 0
    for i in range(len(L)):
        for j in range(i + 1, len(L)):
            if L[i] == L[j]:
                pairs = pairs + 1
    steps = 0
    m = len(L)
    while m > 1:
        m = m // 2
        steps = steps + 1
    return biggest, pairs, steps


print(report([4, 9, 4, 2, 9, 9]))

Sample Run:

(9, 4, 2)

Give the class of the function in terms of the length of L.

The triangular nested loop: 4950 passes on a hundred items

A nested loop whose inner range depends on the outer counter. It does strictly less work than a full pair of nested loops, and the question is whether that changes the class.

def count_inner(n):
    """Assumes n is an int >= 0.
    Returns how many times the inner line of the nested loop runs.
    """
    total = 0
    for i in range(n):
        for j in range(i):
            total = total + 1
    return total


for n in [4, 10, 100]:
    print('n =', n, 'inner line ran', count_inner(n), 'times, n*n is',
          n * n)

Sample Run:

n = 4 inner line ran 6 times, n*n is 16
n = 10 inner line ran 45 times, n*n is 100
n = 100 inner line ran 4950 times, n*n is 10000

Give the exact count and the class, and say how the count compares with n times n.

Five names, one scan against one dictionary

Two ways to answer where is this name in the list. The first walks the list and counts the names it read. The second builds a dictionary from name to position once, and then reaches the answer directly.

def build_index(names):
    """Assumes names is a list of strings.
    Returns a dictionary that maps each name to its position in the list.
    """
    index = {}
    for i in range(len(names)):
        index[names[i]] = i
    return index


def position_by_scan(names, wanted):
    """Assumes names is a list of strings.
    Returns the position of wanted and the number of names looked at.
    """
    looked = 0
    for i in range(len(names)):
        looked = looked + 1
        if names[i] == wanted:
            return i, looked
    return -1, looked


names = ['ada', 'boran', 'ceren', 'deniz', 'eren']
print(position_by_scan(names, 'eren'))
index = build_index(names)
print(index)
print(index['eren'])

Sample Run:

(4, 5)
{'ada': 0, 'boran': 1, 'ceren': 2, 'deniz': 3, 'eren': 4}
4

Give the cost of each design for k searches over a list of n names, and find the k at which they are level.