Ten Lines, Two That Decide: Reading Theta Off a Function

Which lines of a function actually decide its Theta, and how does the dominant term sort any code into one of six complexity classes?

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

Tally the operations as f runs

f_counted is the video's f with an ops counter added. Use the video's counting rules: each = False assignment is 1, each loop pass is 4 (next value of i, two indexings, one ==), setting a flag to True is 1 more, and the final and plus return is 2. Add the missing ops updates so that f_counted(L, L1, L2) returns the pair (result, ops).

def f_counted(L, L1, L2):
    ops = 0
    inL1 = False
    for i in range(len(L1)):
        if L[i] == L1[i]:
            inL1 = True
    inL2 = False
    for i in range(len(L2)):
        if L[i] == L2[i]:
            inL2 = True
    # add to ops wherever the counting rules say an operation happens
    return inL1 and inL2, ops

def f_counted(L, L1, L2):
    ops = 0
    inL1 = False
    for i in range(len(L1)):
        if L[i] == L1[i]:
            inL1 = True
    inL2 = False
    for i in range(len(L2)):
        if L[i] == L2[i]:
            inL2 = True
    # add to ops wherever the counting rules say an operation happens
    return inL1 and inL2, ops

Python runs in your browser

⌘/Ctrl + Enter runs

returns a (result, ops) pair with the right result

counts the worst case, where every position matches

counts a run where nothing matches

counts empty L1 and L2

←Previous Reading Theta Off the Loops: Two Laws and Six Complexity Classes Next A Loop in Constant Time, a Linear One-Liner: Name the Input First →