O(log n)

Python · Unit 22: Complexity

There is a pace much cheaper than O(n): throwing away half of what's left on every step.

From 1024 down to 1, cutting in half, takes only 10 steps. That label is O(log n).

n = 1024
steps = 0
while n > 1:
    n = n // 2
    steps += 1
print(steps)

Prints

The rest of the explanation is in the lesson, which is part of the full plan.

Exercises in this lesson

You do them in the app, which checks them on the spot and explains why.

1. Predict the output
What does this code print?
2. Predict the output
What does this code print?
3. Multiple choice
You have a sorted list with a million numbers and on each step you keep the half where the one you want can be. Roughly how many steps do you need?
4. Complete the code
Complete it to look at the number halfway between low and high.
5. Put the lines in order
Put together a function that counts how many times n can be cut in half before reaching 1.
6. Find the bug
It should count how many times 64 is cut in half before reaching 1, that is 6. Which line has the error?
7. Multiple choice
Which label does sorted(nums) get?
8. Predict the output
What does this code print?

It opens in your browser. This lesson is part of the full plan; the first unit of each course is free.