Timedora
Free Practice Quiz Question List

07 — Efficiency and Computational Complexity Online Quiz Questions

Use this free practice quiz with 20 questions to review 07 — Efficiency and Computational Complexity, test your knowledge, and prepare for your next test or exam.

20 questions
01
Choose one
1 point

Which statement best describes time complexity?

  1. A

    The exact number of seconds on one particular computer

  2. B

    How computational work grows as input size increases

  3. C

    Only the amount of memory needed to store the input

  4. D

    The number of programmers required to implement the algorithm

02
Choose one
1 point

A program uses binary search instead of linear search on an array. Which additional condition is required for the binary-search running-time guarantee described in the material?

  1. A

    The array must contain no duplicate values

  2. B

    The array must have constant-size elements

  3. C

    The array must be sorted

  4. D

    The array must be stored on disk

03
Choose one
1 point

One part of an algorithm takes Θ(n) time and a later part takes Θ(n²) time. What is the asymptotic time complexity of the complete sequence?

  1. A

    Θ(1)

  2. B

    Θ(n)

  3. C

    Θ(n log n)

  4. D

    Θ(n²)

04
Choose all
1 point

Select all statements that are correct about asymptotic notation.

  1. A

    Big-O describes an asymptotic upper bound.

  2. B

    Big-O automatically means worst-case analysis.

  3. C

    Big-Theta describes an asymptotically tight bound.

  4. D

    Big-Omega automatically means best-case analysis.

05
Choose all
1 point

Select all statements that correctly describe auxiliary-space examples from the material.

  1. A

    A maximum-element scan can use Θ(1) auxiliary space.

  2. B

    Copying an array into a second array uses Θ(1) additional space.

  3. C

    Copying an array into a second array uses Θ(n) additional space.

  4. D

    Auxiliary space always includes the memory already required to store the input.

06
True or false
1 point

True or false: Average-case complexity cannot be defined meaningfully without stating assumptions about the distribution of inputs.

  1. A

    True

  2. B

    False

07
True or false
1 point

True or false: Big-O notation automatically means that the analysis is a worst-case analysis.

  1. A

    True

  2. B

    False

08
Written response
1 point

What is the two-word term for memory used by an algorithm in addition to the memory already needed to store its input?

09
Written response
1 point

A program has three nested loops, and each loop runs through n values with constant-time work in the innermost body. Enter the integer exponent k in the resulting Θ(n^k) running time.

10
Fill in the blank
1 point

Complete the complexity statements for linear search: If the target is at the first position, the best-case complexity is . If the target is absent or at the last position, the worst-case complexity is .

11
Fill in the blank
1 point

Complete the analysis of merge sort. Its recurrence is , and its running time is .

12
Open ended
1 point

Explain the time–space trade-off in repeated membership testing. Compare scanning an unsorted array, sorting and then using binary search, and building a hash table. Include the relevant asymptotic costs and describe when different choices may be preferable.

13
Choose one
1 point

A loop starts with a positive value n and repeatedly replaces it with floor(n/2) until it is at most 1. What is the loop's asymptotic number of iterations?

  1. A

    Θ(1)

  2. B

    Θ(log n)

  3. C

    Θ(n)

  4. D

    Θ(n²)

14
True or false
1 point

True or false: Big-O notation automatically means that an algorithm's worst-case running time is being described.

  1. A

    True

  2. B

    False

15
Choose one
1 point

A program replaces linear search with binary search on an array. Which additional condition is required for the binary search to achieve its stated logarithmic search strategy?

  1. A

    The array must contain only distinct values

  2. B

    The array must be stored in consecutive memory locations

  3. C

    The array must be sorted

  4. D

    The array must have an even number of elements

16
Written response
1 point

What technical term names the additional memory used by an algorithm, excluding the memory already required to store its input?

17
Choose one
1 point

Consider a loop that starts with a positive value n and repeatedly replaces n with floor(n / 2) until n is at most 1. What is the loop's running-time growth?

  1. A

    Theta(1)

  2. B

    Theta(log n)

  3. C

    Theta(n)

  4. D

    Theta(n squared)

18
Choose one
1 point

An algorithm performs one sequential phase taking Theta(n) time and a second sequential phase taking Theta(n squared) time. What is the total asymptotic running time?

  1. A

    Theta(1)

  2. B

    Theta(n)

  3. C

    Theta(n squared)

  4. D

    Theta(n cubed)

19
Written response
1 point

In a successful linear search of an array with 9 elements, suppose the target is equally likely to be in any position. What is the expected number of inspected elements? Enter the exact number; no tolerance is allowed.

20
Choose one
1 point

A divide-and-conquer algorithm satisfies the recurrence T(n) = 2T(n/2) + Theta(n). Which asymptotic running time follows for sufficiently large n?

  1. A

    Theta(n)

  2. B

    Theta(n log n)

  3. C

    Theta(n squared)

  4. D

    Theta(2 to the n)