Efficiency of algorithms

Overview

What efficiency means, why steps are counted rather than timed, how growing data changes the picture, two ways to sum 1 to 100 or test 101 for prime, and memory as a second measure.

What you need to know

Answer each one before you reveal it.

Questions from this subtopic

Each one with the model answer underneath.

1. 1

   Can more than one algorithm solve the same problem?

   Model answer

   Many different algorithms can solve the same problem. A list can be sorted by a bubble sort, a merge sort or several other methods.

2. 2

   What is meant by the efficiency of an algorithm?

   Model answer

   Efficiency is how much time or memory an algorithm needs to complete its task. A more efficient algorithm solves the same problem with fewer resources.

3. 3

   What is time efficiency?

   Model answer

   Time efficiency is how quickly an algorithm completes its task. Time efficiency is judged by how many steps the algorithm carries out.

4. 4

   Why are algorithms compared by counting steps rather than timing them with a stopwatch?

   Model answer

   The time a program takes depends on the computer that runs it. The number of steps depends only on the algorithm, so it gives a fair comparison.

5. 5

   Why does efficiency matter more as the amount of data grows?

   Model answer

   A small difference in steps per item becomes a huge difference over millions of items. An inefficient algorithm can become too slow to use on large data sets.

6. 6

   Two algorithms find the sum of the whole numbers from 1 to 100. One adds them in a loop and one calculates 100 × 101 ÷ 2. Which is more time efficient?

   Model answer

   The formula is more time efficient, because it takes the same few steps for any size of problem. The loop needs 100 additions, and more as the numbers grow. Each method gives 5,050.

Other ways to work this

The same content, four other ways.

What is inside Levo

Six ways to work the same material.