Algorithmic Efficiency MCQ Practice

Question 1 of 10

Algorithm L checks list items one by one from the start until it finds a target or finishes all n items. In the worst case for n = 8, how many item checks does L perform?

  1. A. 8
  2. B. 64
  3. C. 1
  4. D. 4

Question 2 of 10

A sorted list has n = 16 values. Binary search roughly halves the remaining region each check. Starting with 16 values, how many halvings until at most one value remains if each step halves exactly (16→8→4→2→1)?

  1. A. 2
  2. B. 4
  3. C. 16
  4. D. 32

Question 3 of 10

For the same sorted list of n items, as n grows, which statement is true when comparing a full linear scan to binary search?

  1. A. Linear scan always needs fewer checks than binary search for large n
  2. B. Both always need exactly 2 checks for every n
  3. C. A full linear scan needs about n checks; binary search needs far fewer checks as n grows
  4. D. Binary search always needs exactly n checks

Question 4 of 10

Algorithm A uses 3n steps for input size n. Algorithm B uses n^2 steps. For n = 5, which is true?

  1. A. A uses 15 steps and B uses 10 steps, so A uses more steps
  2. B. Both use 5 steps
  3. C. Both use 125 steps
  4. D. A uses 15 steps and B uses 25 steps, so B uses more steps

Question 5 of 10

Efficiency in this course is often discussed by counting:

  1. A. how many times statements execute for a given input size
  2. B. only the font size of the source code
  3. C. the number of comments in a program
  4. D. whether the programmer liked the variable names

Question 6 of 10

The table compares step counts.

n Algorithm P steps Algorithm Q steps
2 4 8
4 8 32
6 12 ?

P uses 2n steps. Q uses 2 * n^2 steps. What is Q for n = 6?

  1. A. 36
  2. B. 72
  3. C. 64
  4. D. 12

Question 7 of 10

Two correct algorithms solve the same problem. Algorithm F takes 50 steps for a certain input. Algorithm G takes 12 steps for that same input. Which statement follows?

  1. A. Both algorithms must take 50 steps on every input
  2. B. Step counts cannot be used to compare algorithms
  3. C. Different correct algorithms can have different efficiencies
  4. D. Only incorrect algorithms can differ in step counts

Question 8 of 10

Algorithm Exp checks every subset of an n-element set and uses about 2^n checks. Algorithm Lin uses about n checks. For n = 10, which comparison is correct?

  1. A. Exp uses about 10 checks while Lin uses about 1024
  2. B. Both use exactly 10 checks
  3. C. Both use exactly 2 checks
  4. D. Exp uses about 1024 checks while Lin uses about 10, so Exp uses far more

Question 9 of 10

A heuristic route finder quickly returns a good path that is not guaranteed to be the shortest. When is a heuristic most appropriate?

  1. A. When an exact optimal method is impractical because it would take too many steps for the needed input sizes
  2. B. When every answer must be proven optimal and time is unlimited for any n
  3. C. When the problem has only one possible input of size 1
  4. D. When counting steps is forbidden

Question 10 of 10

For n = 7, a linear scan of all items performs how many item inspections in the worst case?

  1. A. 3
  2. B. 7
  3. C. 49
  4. D. 1