O(1) and O(n)

Python · Unit 22: Complexity

When the steps grow just like the data, you write O(n) and say "order of n". It is a label for the pace, not for the exact number.

They are the same labels every challenge in the app carries: O(1), O(log n), O(n), O(n log n), O(n²) and O(2ⁿ), from cheapest to most expensive.

cart = [12, 5, 9]
steps = 0
for p in cart:
    steps += 1
print(steps, len(cart))

Prints

3 3

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. Multiple choice
nums is a list of numbers. Which of these costs the same with 3 numbers as with a million?
3. Predict the output
What does this code print?
4. Complete the code
Complete it to return the last price without walking the list.
5. Predict the output
What does this code print?
6. Put the lines in order
Put together an O(n) function that counts how many even numbers the list holds.
7. Find the bug
It should print the first and the last number of the list. Which line has the error?
8. Find the case that fails
contains(nums, x) should return True if x is in the list and False if it isn't, looking one by one. Which call breaks it?
9. Multiple choice
Both return the last number of the list. Which one is O(1)?

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