Counting operations
Counting the elementary operations of a piece of code as a function of the size n: a simple loop, successive loops, nested loops, a dependent loop and a loop that halves.
- 25 cards
- 6 topics
- Free
The outline, topic by topic
Each topic is weighted the way the exam weighs it.
- Concepts
- Questions
- Sort and link
- The numbers
- Scenarios
- Understand
A few cards from the deck
Elementary operation: what is it?
Show the answer
An operation whose time does not depend on the size of the data: addition, comparison, assignment, reading one cell of an array.
Each such operation is counted once. A statement like
x in ton a list is not one: it compares up to n elements.What does this program print?
```python
c = 0
for i in range(5):
for j in range(5):
c += 1
print(c)`2510520
Show the answer
25The inner loop makes 5 passes for each of the 5 passes of the outer one: 5 × 5 = 25. Adding the passes (5 + 5) is the classic mistake.
A loop of n passes with a fixed number of operations per pass costs about … operations; two nested loops of n passes each cost about … operations.
Show the answer
A loop of n passes with a fixed number of operations per pass costs about n operations; two nested loops of n passes each cost about n² operations.
Nested loops: multiply the numbers of passes (n × n). Loops that follow one another: add them, n + n = 2n.
Input size: what is it?
Show the answer
The quantity that measures how large the data to process is, written n: for instance the number of cells of an array.
The cost of an algorithm is expressed as a function of n. For an array of 20 cells, n is 20; for a text, it is the number of characters.