Order of Growth: What to Measure, Which Input, and the Worst Case

If timing and counting both work, why aren't they enough, and which input and which case should an efficiency claim be about?

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

Name the behaviour behind a count column

costs holds one function's operation counts at inputs 10, 100, 1,000 and 10,000, each ten times the one before. Small inputs can hide the growth, so let the largest inputs decide. Define behaviour(costs) returning exactly one of the strings 'constant', 'linear', 'quadratic' or 'logarithmic'.

def behaviour(costs):
    # costs were measured at inputs 10, 100, 1000 and 10000, in that order.
    return ...  # your code here

def behaviour(costs):
    # costs were measured at inputs 10, 100, 1000 and 10000, in that order.
    return ...  # your code here

Python runs in your browser

⌘/Ctrl + Enter runs

returns one of the four names

reads the convert_to_km, sum_of and is_in columns

reads the diameter, square and binary search columns

lets the largest inputs decide

←Previous Counting Operations: Exact Formulas and a Program That Counts Itself Next Big O: An Upper Bound That Only Has to Hold Past the Crossover →