Algorithm Efficiency CS Thinking Example 1

Follow the full solution, then compare it with the other examples linked below.

Example 1

hard
Algorithm A takes 100 steps for an input of size 10 and 400 steps for size 20. Algorithm B takes 10 steps for size 10 and 20 steps for size 20. Which is more efficient and what might their time complexities be?

Solution

  1. 1
    Step 1: Algorithm A: when size doubles (10→20), steps quadruple (100→400). This suggests O(n2)O(n^2).
  2. 2
    Step 2: Algorithm B: when size doubles, steps double (10→20). This suggests O(n)O(n).
  3. 3
    Step 3: Algorithm B is more efficient — it grows linearly while A grows quadratically.

Answer

Algorithm B is more efficient: O(n)O(n) vs O(n2)O(n^2).
Efficiency measures how an algorithm's resource usage (time or space) grows with input size. Linear growth (O(n)O(n)) is much better than quadratic (O(n2)O(n^2)) for large inputs.

About Algorithm Efficiency

The ratio of useful output energy (or power) to total input energy, expressed as a percentage — always less than 100% due to energy losses.

Learn more about Algorithm Efficiency →

More Algorithm Efficiency Examples

Example 2 hard

Explain why binary search ([formula]) is more efficient than linear search ([formula]) for a sorted

Example 3 hard

Rank these time complexities from most to least efficient: [formula], [formula], [formula], [formula

Example 4 hard

Algorithm X checks every pair of students in a class of size `n`. Algorithm Y checks each student on

← All Algorithm Efficiency Examples Algorithm Efficiency Concept