Practice set: counting steps and growth

P1. Adding 20 numbers needs how many additions?

• 19
• 20
• 21
• 10

P2. Comparing every pair among 7 items needs:

• 21 comparisons
• 7 comparisons
• 49 comparisons
• 14 comparisons

P3. A linear method costs 300 steps at n = 100. At n = 200 it costs about:

• 600 steps
• 300 steps
• 1,200 steps
• 900 steps

P4. A quadratic method costs 400 steps at n = 20. At n = 40 it costs about:

• 1,600 steps
• 800 steps
• 400 steps
• 3,200 steps

P5. For A = 100n and B = n×n, at n = 100:

• They cost the same
• A is cheaper
• B is cheaper
• Neither can be computed

P6. 2 to the power 5 equals:

• 32
• 10
• 25
• 16

P7. Binary search is an example of which growth?

• Logarithmic
• Quadratic
• Linear
• Exponential

P8. Which is the best question to ask about a method before using it on a large input?

• How does its cost grow with n?
• How long is its code?
• Who wrote it?
• What colour is the output?