๐Ÿ“˜ CodingMarble Learn

Algorithm Analysis: Which Inputs and Which Results Are Possible?

To analyse an algorithm means to study what it does. You trace it for one input, step by step. Then you ask: what results can it give for all allowed inputs, and which input gave a certain result? Working backwards undoes the steps in reverse order. Some results are impossible, and sometimes two inputs give the same result.

๐ŸŽฌ Step-by-step story

  1. An algorithm is a list of steps. Ours has two: first multiply by 2, then add 3. Nothing has gone in yet.
  2. Put in the input x = 4. The ball becomes 8 after the first step and 11 after the second. 11 is the result.
  3. Try x = 5. The same steps now give 13. Same algorithm, different input, different result.
  4. Now run every input from 0 to 9. The green cells are all the results the algorithm can give. They are all odd numbers.
  5. Go backwards from the result 11: take away 3 to get 8, then halve it to get 4. Now try 10: it is impossible, because 7 cannot be halved into a whole number.
  6. Your turn. Move the slider, watch the result, and decide which cells could never turn green.

Tip: drag the 3D scene to turn it. Use two fingers to zoom.

๐Ÿค” Common doubts, cleared

What is the difference between input and result?

The input goes in at the start (the blue cube). The result comes out at the end (the green cell).

Does a different input always change the result?

For this algorithm yes: x = 4 gives 11 and x = 5 gives 13. With a choice inside the algorithm, two inputs can meet at one result.

How do I know all the possible results?

Trace every allowed input and collect the results. The green cells show them. Then look for a pattern, such as all being odd.

Why do I undo the steps in reverse order?

The last thing done is the first thing to take back, like socks and shoes: you put on socks, then shoes, so to undo it you take off the shoes first, then the socks.

What if going backwards gives a fraction?

Then that result is impossible for whole-number inputs. See the red cell for 10: 7 รท 2 is 3.5.

What is algorithm analysis?

An algorithm is a list of steps that solves a task. Analysing an algorithm means studying it carefully: what does it do, and what can happen?

The data you give at the start is the input. What comes out at the end is the result (also called output). To see what an algorithm does, you trace it: you do each step by hand and write down the value after each step.

From input to result: tracing one case

Take the algorithm: read x, multiply it by 2, add 3, give the result.

  1. Input x = 4
  2. After step 1: 4 ร— 2 = 8
  3. After step 2: 8 + 3 = 11
  4. Result: 11

Write the values in a small table. A table shows quickly where something went wrong. If the algorithm has a choice (if x is bigger than 10 ...), say which branch you took.

All possible results

Often we ask: what results can this algorithm give? First find out which inputs are allowed (for example whole numbers from 0 to 9). Then trace every input and collect the results.

For x ร— 2 + 3 the results are 3, 5, 7, 9 ... 21. Every one is odd, because x ร— 2 is always even and adding 3 makes it odd. So you can say an even result is impossible without testing every input. Spotting such a pattern is the real skill of analysis.

Which input gave this result? Going backwards

To find the input from a result, undo the steps in reverse order. The forward steps were ร— 2, then + 3. So backwards: first โˆ’ 3, then รท 2.

Result 11: 11 โˆ’ 3 = 8, 8 รท 2 = 4. Input was 4. Check by going forward again: 4 ร— 2 + 3 = 11. Always check.

If going backwards gives a number that is not allowed (a fraction, a negative number, a number outside the range), then that result is impossible. Result 10: 10 โˆ’ 3 = 7, 7 รท 2 = 3.5, not a whole number, so impossible.

When two inputs give one result

Algorithms with a choice can send two different inputs to the same result. Take: if n is more than 10, result = n โˆ’ 10, otherwise result = n ร— 2. Input 2 gives 4. Input 14 gives 4 too. So from the result 4 alone you cannot tell the input. You must list all inputs that could give it.

Key formulas and definitions

Worked examples

1. Algorithm: take x, multiply by 2, add 3. Find the result for x = 7.

7 ร— 2 = 14, then 14 + 3 = 17. The result is 17.

2. The same algorithm gave the result 21. Which input was used?

Go backwards. 21 โˆ’ 3 = 18, and 18 รท 2 = 9. Check: 9 ร— 2 + 3 = 21. The input was 9.

3. Can the same algorithm give the result 12 for a whole-number input?

12 โˆ’ 3 = 9, and 9 รท 2 = 4.5. That is not a whole number. So 12 is impossible. In fact every result is odd, so no even number is possible.

4. Algorithm: if n > 10 then result = n โˆ’ 10, else result = n ร— 2. Find the result for n = 7 and n = 25.

n = 7 is not more than 10, so result = 7 ร— 2 = 14. n = 25 is more than 10, so result = 25 โˆ’ 10 = 15.

5. For the algorithm in the last example, find every input that gives the result 4.

Branch 1 (n โ‰ค 10): n ร— 2 = 4, so n = 2. This is โ‰ค 10, so it is valid. Branch 2 (n > 10): n โˆ’ 10 = 4, so n = 14. This is > 10, so it is valid. The inputs are 2 and 14.

Common mistakes

Practice quiz

1. In algorithm analysis, the data given at the start is called:
2. Algorithm: x ร— 2, then + 3. For x = 6 the result is:
3. To find the input from a result you:
4. Which result is impossible for x ร— 2 + 3 with whole-number x?
5. Doing each step by hand and noting the values is called:

Practice: answer these yourself

Type or choose your answer, then press Check. Use a hint if you are stuck; the full solution appears after you answer.

Frequently asked questions

What is algorithm analysis in simple words?

It is studying an algorithm to find out what it does: what result you get for an input, which results are possible, and which input gave a given result.

How do I find the input if I only know the result?

Go backwards. Undo the last step first and use the opposite operation each time. Then run the algorithm forward to check.

How is this different from algorithm complexity?

Here we ask what the algorithm computes (inputs and results). Complexity asks how many steps it needs as the input grows. Both are part of analysing algorithms.

Learn first

Learn next

Related lessons

All Computer Science lessons