Two Linear Factorials and a Timing Table That Looks Quadratic

If iterative and recursive factorial are both Theta(n), why does the timing table grow faster than linear once the numbers get large?

Finger exercises

Short drills on what this video just taught. Write the code, run the checks, and reveal the answer only if you are stuck.

0 / 5 passed

Exercise 1 of 5

Count the passes of fact_iter

The function below is the video's fact_iter, extended to return the factorial and a counter passes. The counter never moves yet. Add one line so that passes counts every trip through the loop, keeping the function name fact_iter_passes(n).

def fact_iter_passes(n):
    prod = 1
    passes = 0
    for i in range(2, n+1):
        prod *= i
        # count this pass
    return prod, passes

def fact_iter_passes(n):
    prod = 1
    passes = 0
    for i in range(2, n+1):
        prod *= i
        # count this pass
    return prod, passes

Python runs in your browser

⌘/Ctrl + Enter runs

returns a (product, passes) pair

counts the passes for n = 5

counts the passes for larger n

makes no passes for n = 1

←Previous A Loop in Constant Time, a Linear One-Liner: Name the Input First Next Which Loop Depends on n? compound and fib_iter Linear, g Quadratic →