A Loop in Constant Time, a Linear One-Liner: Name the Input First

How can a function with a loop still run in constant time, and why must you always name which input the complexity is measured against?

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

A loop that ignores the list's length

Return the sum of the first five elements of L (assume L has at least five). Use a for loop over range(5) and indexing, so the loop goes round the same number of times however long L gets. Define sum_first_five(L).

def sum_first_five(L):
    # loop a fixed number of times, adding one element per pass
    return ...

def sum_first_five(L):
    # loop a fixed number of times, adding one element per pass
    return ...

Python runs in your browser

⌘/Ctrl + Enter runs

returns an int for a list of ints

adds only the first five elements

reads the same number of elements from a short and a very long list

←Previous Ten Lines, Two That Decide: Reading Theta Off a Function Next Two Linear Factorials and a Timing Table That Looks Quadratic →