Lesson 7.2 · Answer it
Name the growth
5 marksYou mark it yourself against the marking points
Four algorithms, W, X, Y and Z, were each run on an input of size 100 and then of size 200. The table shows how many steps each one took. Each time n doubles again, each algorithm's steps change in the same way as they did from 100 to 200.
| Algorithm | Steps for n = 100 | Steps for n = 200 |
|---|---|---|
| W | 300 | 600 |
| X | 8 | 8 |
| Y | 10000 | 40000 |
| Z | 6 | 7 |
(a) State the smallest Big O class that fits each algorithm, choosing from O(1), O(log n), O(n) and O(n²). [4]
(b) State how many steps Y would take for n = 400. [1]
[5]