Algorithmic Efficiency: Practice Questions (Computer Science Principles 3.17)

These are original Marlbridge practice questions, not past exam questions. All scenarios are fictional. The code is Marlbridge’s rendering of the exam reference notation (← assignment, = equality test, lists start at index 1, DISPLAY shows a value). Mark points are a suggested Marlbridge rubric, not an official scoring guideline. No calculator is needed or allowed. Try each question before opening its answer.

Question 1 (multiple choice · foundation)

How can the efficiency of an algorithm be estimated informally?

(A) By counting the lines of code in the program.
(B) By counting the number of times a statement or group of statements executes.
(C) By measuring the size of the screen.
(D) By counting how many variables are declared.

Answer and explanation

Answer: (B). Efficiency concerns the work done, measured by the number of executions as the input grows.

(A) A short program can run for a long time.
(C) and (D) are unrelated to running time.

Question 2 (multiple choice · core)

Segment P runs a single loop n times. Segment Q runs a loop inside a loop, each n times. For n = 20, how many times does the innermost statement of each run?

n ← 20
count ← 0
REPEAT n TIMES
{
  REPEAT n TIMES
  {
    count ← count + 1
  }
}
DISPLAY(count)

(A) P: 400, Q: 20
(B) P: 20, Q: 40
(C) P: 40, Q: 400
(D) P: 20, Q: 400

Answer and explanation

Answer: (D). A single loop runs n times; a loop inside a loop runs n × n times: 20 × 20 = 400.

(A) swaps them.
(B) adds instead of multiplying.
(C) doubles P and adds.

Question 3 (multiple choice · core)

Which algorithms run in a reasonable amount of time?

(A) Algorithms whose steps grow like 2 to the power n.
(B) Algorithms whose steps grow like n, n squared or n cubed.
(C) Algorithms whose steps grow like n factorial.
(D) Only algorithms that take no steps at all.

Answer and explanation

Answer: (B). Polynomial (and slower-growing) algorithms are reasonable.

(A) and (C) are exponential and factorial: unreasonable for large inputs.
(D) is meaningless.

Question 4 (multiple choice · core)

“What is the shortest route from A to B?” is an example of which kind of problem?

(A) An optimization problem
(B) A decision problem
(C) An instance
(D) An undecidable problem

Answer and explanation

Answer: (A). It asks for the best of many solutions.

(B) A decision problem would ask “Is there a route?” with a yes/no answer.
(C) An instance includes specific input; this is the general problem.
(D) Not suggested by the question.

Question 5 (multiple choice · foundation)

Sorting is a problem. Which is an instance of the sorting problem?

(A) Sorting lists faster
(B) Sorting any list into order
(C) Sorting the list (2, 3, 1, 7)
(D) Sorting by hand

Answer and explanation

Answer: (C). An instance has specific input.

(A) and (D) are not instances.
(B) is the general problem.

Question 6 (multiple choice · core)

When is a heuristic most appropriate?

(A) When the best answer must be guaranteed.
(B) When no efficient algorithm that always finds the best answer is known, and a good approximate answer is acceptable.
(C) When the input is tiny and an exact algorithm is quick.
(D) When the problem is a simple yes/no question about one number.

Answer and explanation

Answer: (B). Heuristics trade a guarantee of optimality for speed.

(A) A heuristic does not guarantee the best answer.
(C) and (D) are easy to solve exactly.

Question 7 (multiple choice · core)

An algorithm needs 2 to the power n steps. By what factor does the number of steps increase when n increases by 1?

(A) 1
(B) n
(C) 2 plus n
(D) 2

Answer and explanation

Answer: (D). 2^(n+1) = 2 × 2^n.

(A) would mean no change.
(B) and (C) do not describe exponential growth.

Question 8 (multiple select, choose two · core)

Which two statements are true?

(A) A faster computer turns an exponential algorithm into a polynomial one.
(B) An algorithm that takes 2 to the power n steps runs in reasonable time for large n.
(C) Algorithms with exponential or factorial growth are unreasonable for large inputs.
(D) Different correct algorithms for the same problem can have different efficiencies.
(E) The efficiency of an algorithm is the number of lines in its code.

Answer and explanation

Answers: (C) and (D). These are two of the standard ideas of the topic.

(A) Speed of the computer does not change growth.
(B) is the opposite of what is true.
(E) Efficiency is about executions, not code length.

Question 9 (constructed response · core)

Consider the segment, with n assigned before it. (a) How many times does count ← count + 1 run when n is 4? (b) When n is 8? (c) Describe the pattern when n doubles. (d) A second segment has only one loop that runs n times. For which segment does the work grow faster, and by how much when n doubles?

count ← 0
REPEAT n TIMES
{
  REPEAT n TIMES
  {
    count ← count + 1
  }
}

Answer and explanation

(a) 4 × 4 = 16.

(b) 8 × 8 = 64.

(d) The nested segment grows faster: its work quadruples when n doubles, while the single-loop segment only doubles.

Suggested Marlbridge rubric (5 marks)

Mark point	Marks
(a) 16	1
(b) 64	1
(c) States that the work quadruples (or is n squared)	1
(d) Identifies the nested segment as growing faster	1
(d) Compares quadrupling with doubling	1

Question 10 (constructed response · stretch)

An algorithm needs 2 to the power n steps for an input of size n, on a computer that does one billion (1,000,000,000) steps per second. (a) Approximately how long does it take for n = 30? (b) For n = 60? (c) Explain why this algorithm is described as running in an unreasonable amount of time, and why buying a computer ten times faster does not solve the problem.

Answer and explanation

(a) 2³⁰ = 1,073,741,824 steps, which is about 1.07 seconds (a reasonable wait).

(b) 2⁶⁰ = 1,152,921,504,606,846,976 steps, which is about 1.15 × 10⁹ seconds, or roughly 36.6 years.

(c) Each increase of n by 1 doubles the time, so the time explodes as the input grows: it goes from about a second to decades when n doubles from 30 to 60. A computer ten times faster reduces 36.6 years to about 3.7 years, but then n only has to increase by about 3 (2³ = 8) to win back most of the loss: 3.7 × 8 is about 29 years. The growth pattern, not the speed of the computer, is the problem.

Suggested Marlbridge rubric (5 marks)

Mark point	Marks
(a) 2^30 ≈ 1.07 billion steps, about 1 second	1
(b) 2^60 ≈ 1.15 × 10^18 steps	1
(b) About 36 years (36.6)	1
(c) Each extra input doubles the time	1
(c) A faster computer only shifts the problem slightly	1

How did you do?

Count the questions you got right first time, then read the explanation for every one you missed, including the wrong options you rejected correctly, because the distractors show you the typical slips. Anything you missed twice goes onto your revision list for the revision notes; re-read the matching section of the study guide before trying again.