Which statement best describes time complexity?
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.
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?
- A
The array must contain no duplicate values
- B
The array must have constant-size elements
- C
The array must be sorted
- D
The array must be stored on disk
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?
- A
Θ(1)
- B
Θ(n)
- C
Θ(n log n)
- D
Θ(n²)
Select all statements that are correct about asymptotic notation.
- A
Big-O describes an asymptotic upper bound.
- B
Big-O automatically means worst-case analysis.
- C
Big-Theta describes an asymptotically tight bound.
- D
Big-Omega automatically means best-case analysis.
Select all statements that correctly describe auxiliary-space examples from the material.
- A
A maximum-element scan can use Θ(1) auxiliary space.
- B
Copying an array into a second array uses Θ(1) additional space.
- C
Copying an array into a second array uses Θ(n) additional space.
- D
Auxiliary space always includes the memory already required to store the input.
True or false: Average-case complexity cannot be defined meaningfully without stating assumptions about the distribution of inputs.
- A
True
- B
False
True or false: Big-O notation automatically means that the analysis is a worst-case analysis.
- A
True
- B
False
What is the two-word term for memory used by an algorithm in addition to the memory already needed to store its input?
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.
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 .
Complete the analysis of merge sort. Its recurrence is , and its running time is .
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.
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?
- A
Θ(1)
- B
Θ(log n)
- C
Θ(n)
- D
Θ(n²)
True or false: Big-O notation automatically means that an algorithm's worst-case running time is being described.
- A
True
- B
False
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?
- A
The array must contain only distinct values
- B
The array must be stored in consecutive memory locations
- C
The array must be sorted
- D
The array must have an even number of elements
What technical term names the additional memory used by an algorithm, excluding the memory already required to store its input?
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?
- A
Theta(1)
- B
Theta(log n)
- C
Theta(n)
- D
Theta(n squared)
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?
- A
Theta(1)
- B
Theta(n)
- C
Theta(n squared)
- D
Theta(n cubed)
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.
A divide-and-conquer algorithm satisfies the recurrence T(n) = 2T(n/2) + Theta(n). Which asymptotic running time follows for sufficiently large n?
- A
Theta(n)
- B
Theta(n log n)
- C
Theta(n squared)
- D
Theta(2 to the n)
Related study packs and tools
2 Digital Logic
A 14-question medium-difficulty quiz on Boolean algebra, logic gates, truth tables, and combinational circuits.
6 Computer Memory
Learn how computer memory stores and addresses information, how RAM and ROM differ, and how caches and the memory hierarchy balance speed, capacity, and cost.
6 Trees and Binary Search Trees
A 14-question quiz on trees, binary trees, traversals, recursive algorithms, and binary search trees. The questions progress from foundational concepts to applied reasoning about structure, complexity, and BST operations.
07 Trees and Binary Search Trees
A progressive guide to tree structure, binary-tree traversals, binary search tree operations, deletion, balancing, and the way tree height determines time and space costs.
8 Software Documentation
Learn how to choose, structure, document, and maintain software documentation for users, developers, integrators, and operators.
9 Sorting Algorithms
A structured guide to comparison-based sorting algorithms, their complexity, stability, memory use, and practical selection criteria.
Interrupts
Reviews how interrupts support event handling and multitasking, and how Linux system calls use the RISC-V `ecall` instruction and register conventions.
OS Processes
This quiz covers process management, context switching and scheduling, multitasking, traps and interrupts, and RISC-V privilege transitions.
Systemcalls
A quiz on operating-system system calls, including privileged-operation requests, process creation and execution with fork, exec, and waitpid, and signal handling.