Working out a complexity
Counting the operations of iterative code: statements in sequence, a single loop, nested loops, a halving loop, a hidden call inside a loop, best and worst case, memory used.
- 19 cards
- 3 topics
- Free
The outline, topic by topic
Each topic is weighted the way the exam weighs it.
- Concepts
- Questions
- Sort and link
A few cards from the deck
Elementary operation: what is it?
Show the answer
A statement whose cost does not depend on the size of the data: an assignment, a comparison, an addition, an access to an array cell.
It is the unit we count. Beware of statements that are not:
x in items,items.count(x)ormax(items)walk the whole list and cost O(n).What is the time complexity of this function?
```python
def f(n):
c = 0
for i in range(n):
for j in range(n):
c += 1
for k in range(n):
c += 1
return c`- O(n²)
- O(n³)
- O(n)
- O(n log n)
Show the answer
O(n²)
The double block does n² increments, the final loop n: n² + n operations, whose dominant term is n². The loops do not make n³ since the last one is not nested: its cost adds instead of multiplying.
Two loops of n iterations: if nested, the body runs … times; if one follows the other, it runs … times in all, which is O(n).
Show the answer
Two loops of n iterations: if nested, the body runs n² times; if one follows the other, it runs 2n times in all, which is O(n).
Nested loops: the iteration counts multiply. Loops in sequence: they add up.
Worst case: what is it?
Show the answer
The maximum cost of an algorithm over all possible inputs of a given size n.
It is a guarantee: no input of size n will cost more. For a sequential search, it is the element in last place or absent.
How many iterations does this loop make, as a function of n?
```python
i = 1
while i < n:
i = i * 2`- O(n)
- O(log n)
- O(√n)
- O(n log n)
Show the answer
O(log n)
i takes 1, 2, 4, 8…: it doubles at each turn and reaches n after about log₂ n turns. An index moving by 1 would give O(n), but here it jumps further and further.