4.4.4.1 Comparing algorithms Quiz: AQA Computer Science, Unit 4

The 20 questions

1. Algorithms can be compared by expressing their complexity as a function of what?

   • The name of the programmer
   • The date the algorithm was written
   • The size of the problem
   • The colour of the screen

2. In which two respects can one algorithm be more efficient than another?

   • Time-wise and space-wise
   • Legally and commercially
   • Alphabetically and numerically
   • Visually and audibly

3. Efficiently implementing automated abstractions means designing models and algorithms to run quickly while using what?

   • The minimal amount of resources such as memory
   • Random numbers
   • Only the cheapest hardware available
   • The maximum amount of memory available

4. Algorithm A is fast but uses a lot of memory, and algorithm B is slower but uses little memory. Which statement is correct?

   • They cannot be compared at all
   • Each is more efficient in a different respect, so neither is best in every way
   • A is more efficient in every respect
   • B is more efficient in every respect

5. What does 'more efficient time-wise' mean?

   • It is written in fewer lines of code
   • It has a more attractive interface
   • It runs in less time for the same problem
   • It uses more memory

6. Algorithm A performs n^2 steps and algorithm B performs 100n steps. For n = 10, which performs fewer steps?

   • Neither performs any steps
   • They perform the same number of steps
   • A, with 100 steps
   • B, with 1000 steps

7. For the same algorithms (n^2 and 100n), at what value of n do they perform equal numbers of steps?

   • 10
   • 100
   • 50
   • 1000

8. Which algorithm is more efficient time-wise for very large n: one with O(n) time or one with O(n^2) time?

   • The O(n^2) algorithm
   • They are equally efficient
   • The O(n) algorithm
   • Neither, because n is large

9. For n = 1024, which sort needs roughly fewer comparisons: bubble sort or merge sort?

   • Merge sort
   • They need the same number
   • Neither needs comparisons
   • Bubble sort

10. Algorithm X uses O(n) memory and algorithm Y uses O(1) memory. Which is more space-efficient?

    • Y, because it uses a fixed amount of memory
    • They are equally space-efficient
    • X, because it uses more memory
    • Neither uses any memory

11. An O(n) algorithm takes 3 seconds on n items. Roughly how long does it take on 2n items?

    • 9 seconds
    • 6 seconds
    • 3 seconds
    • 12 seconds

12. An O(n^2) algorithm takes 3 seconds on n items. Roughly how long does it take on 2n items?

    • 12 seconds
    • 6 seconds
    • 24 seconds
    • 9 seconds

13. Why is comparing algorithms by measured seconds on one computer less useful than comparing complexity functions?

    • Timings are never measured in seconds
    • Complexity functions are always measured in seconds
    • Seconds cannot be compared at all
    • Timings depend on the hardware, whereas growth functions describe the algorithm itself

14. Which measure of an algorithm does not depend on the hardware used?

    • The brand of processor used
    • The screen resolution of the computer
    • Counting the basic steps performed as a function of n
    • The number of seconds on a particular laptop

15. Algorithm A performs 5n + 20 operations and algorithm B performs n^2 operations. For large n, which is more efficient?

    • B, because its growth is quadratic
    • Neither, because n is large
    • A, because its growth is linear
    • They are equally efficient for large n

16. Algorithm A takes 2^n steps and algorithm B takes n^3 steps. As n grows, which becomes impractical first?

    • B, because cubic growth is always faster than exponential growth
    • Neither becomes impractical
    • Both become impractical at the same n
    • A, because exponential growth outpaces polynomial growth

17. Roughly how many times more operations does bubble sort need than merge sort for one million items?

    • About 20
    • About 50,000
    • About 2
    • About 1,000,000

18. Merge sort uses extra memory for its merges, whereas bubble sort sorts in place. Which trade-off does this illustrate?

    • Time efficiency gained at the cost of extra space
    • Speed and accuracy in the output
    • No trade-off exists
    • Space efficiency gained at the cost of extra time for no reason

19. Why might a slower algorithm sometimes be preferred?

    • It never needs testing
    • It is faster for every input size
    • It always has better complexity
    • It may use less memory or be simpler to implement for small inputs

20. Which statement about Big-O comparisons is correct?

    • They give exact running times for every input
    • They describe growth for large n, and constant factors can still matter for small n
    • They ignore the size of the problem entirely
    • They are only useful when n equals 1

Related quizzes

• Problem-solving and algorithms Quiz · 4.4.1.1 · 20 questions
• Abstraction Quiz · 4.4.1.3 · 20 questions
• Problem reduction and decomposition Quiz · 4.4.1.8 · 20 questions
• Composition Quiz · 4.4.1.10 · 20 questions
• Automation Quiz · 4.4.1.11 · 20 questions
• Finite state machines Quiz · 4.4.2.1 · 20 questions
• Regular expressions Quiz · 4.4.2.3 · 20 questions
• Backus-Naur Form and syntax diagrams Quiz · 4.4.3.1 · 20 questions
• Order of complexity Quiz · 4.4.4.3 · 20 questions
• Limits of computation and computable problems Quiz · 4.4.4.4 · 20 questions