Programming Basics: Count the Work

Compare operation counts under a clearly stated cost model.

All worksheets

5 questions0m 0s

Learn the skill

Count only SHOW executions. A single REPEAT n TIMES loop containing one SHOW performs n shows. Two nested loops, each REPEAT n TIMES, with one SHOW in the inner body perform n squared shows. n is a nonnegative integer; this is not a wall-clock prediction.

Worked example

For n = 4, the single loop performs 4 shows and the nested loops perform 16. Doubling n doubles the first count but quadruples the second count.

For input size four, a single loop executes SHOW four times and two nested loops execute SHOW sixteen times. Doubling the input to eight gives eight and sixty-four shows respectively.

Would you believe it?

A loop can execute its body zero times. Skipping the body does not skip the whole program: later instructions can still run.

Python documentation: loops

Question 1 For n = 5, how many shows does the single loop perform? 5 25 10

Question 2 For n = 5, how many shows do the two nested loops perform? 10 5 25

Question 3 For n = 0, how many shows do the nested loops perform? 2 0 1

Question 4 When n doubles, the nested-loop SHOW count changes by what factor? 4 2 8

Question 5 Does this count alone tell exact elapsed seconds? Yes Only when n is even No

Review your work

0correct

Complete the questions to review each answer.

View dashboard