Two Nested Loops, Three Thetas: diameter, all_digits, and a Hidden in

Why is one nested loop quadratic, another only linear, and a third secretly cubic because of a single in check?

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

Average passes of the shrinking loop

These are the two loop headers of diameter, written for a list of n points:

for i in range(n):
    for j in range(i+1, n):
        ...

Count every pass of the inner loop, then divide by the number of outer passes to get the average run of the inner loop. Define average_inner(n) returning that average as a float (you may assume n is at least 1).

def average_inner(n):
    # your code here
    return ...

def average_inner(n):
    # your code here
    return ...

Python runs in your browser

⌘/Ctrl + Enter runs

returns a float

is 0.0 for a single point

matches the staircase for 8 points

stays close to half of n for 200 points

←Previous Nested Loops Over Two Lists: is_subset, intersect, and Nine Sevens Next Two Calls Per Call: Recursive Fibonacci and the Cost of All Subsets →