← All lessons

Complexity: O(1) and O(n)

Sign in · Sign up

Lesson 12.0

Two ways of getting to data differ in speed. The speed of an algorithm is described like this: how many steps it takes depending on the size of the data. That is what O(...) means.

numbers = list(range(1000))

print(numbers[500])     # O(1) — straight by index
print(999 in numbers)   # O(n) — the whole list is scanned
  • numbers[500] does not depend on the length of the list: the list knows where the item sits, that is O(1);
  • 999 in numbers goes through the items until it finds it: in the worst case n steps, that is O(n);
  • O is not seconds but the growth of the number of steps: O(1) is a flat line on a graph, O(n) rises with the size.

The check gives the list numbers, the index index and the number target. Print:

  1. the item by index — numbers[index];
  2. True or False — whether target is in the list;
  3. where target first appears — numbers.index(target);
  4. -1 if the number is absent: numbers.index raises in that case, so the check is needed before the call.

The third line shows how many steps the list had to go through: that is O(n).

Hint

An index is the number in square brackets, the item is taken with [index].

Presence is checked with the word in: target in numbers gives True or False. Where the item first appears is told by numbers.index(target), but if the item is missing it raises an error — so checking with in first is worth it.