When analyzing an algorithm that sorts a collection of records, what is the most appropriate interpretation of the input-size variable ?
09. Evaluating Algorithm Efficiency Online Quiz Questions
Use this free practice quiz with 20 questions to review 09. Evaluating Algorithm Efficiency, test your knowledge, and prepare for your next test or exam.
A procedure performs one loop over n items and then a second loop over n items. What is its asymptotic time complexity?
- A
O(1)
- B
O(logn)
- C
O(n)
- D
O(n2)
Consider two nested loops where both the outer and inner loop execute exactly n times. What is the asymptotic time complexity?
- A
O(n)
- B
O(logn)
- C
O(n2)
- D
O(2n)
Select all statements that correctly describe asymptotic notation.
- A
Big-O describes an asymptotic upper bound.
- B
Big-O automatically means worst-case analysis.
- C
Big-Theta describes matching asymptotic upper and lower bounds.
- D
Big-Theta retains all constant factors and lower-order terms.
Select all correct statements about the best and worst cases of linear search through an array.
- A
A target at the first position gives best-case O(1).
- B
A target at the first position gives worst-case O(n).
- C
A target at the last position gives best-case O(1).
- D
A target at the last position or an absent target gives worst-case O(n).
True or false: Saying that an algorithm is O(n) automatically means that its worst-case running time is linear.
- A
True
- B
False
True or false: A loop that repeatedly replaces its remaining problem size with ⌊n/2⌋ has O(logn) time complexity.
- A
True
- B
False
A loop runs from i=1 through i=n, inclusive. For n=1, how many times does the loop body execute? Enter a whole-number count.
Complete the statements: The resource measure for computational work is , while the resource measure for memory use is .
Complete the statement: The dominant growth class of T(n)=4n2+7n+12 is .
Analyze the following procedure, assuming A contains n values: it initializes sum to zero, scans every value x in A, adds x to sum, and returns sum. State its asymptotic running time and its auxiliary space complexity, and explain the difference between the input array's space and auxiliary space.
An algorithm executes an inner operation 1 time during the first outer iteration, 2 times during the second, and so on through n times during the last. What is the tight asymptotic complexity?
- A
Θ(n)
- B
Θ(n2)
- C
Θ(nlogn)
- D
Θ(2n)
An algorithm allocates a new array of length n and copies the input array into it. What is the algorithm's auxiliary space complexity?
- A
O(n)
- B
O(1)
- C
O(logn)
- D
O(n2)
A duplicate-detection algorithm compares every pair of elements and returns only after all pairs have been checked when no duplicate exists. It uses two index variables and no additional array. Which classification is correct?
- A
Worst-case time Θ(n) and auxiliary space Θ(n)
- B
Worst-case time Θ(n2) and auxiliary space Θ(n)
- C
Worst-case time Θ(n2) and auxiliary space Θ(1)
- D
Worst-case time Θ(2n) and auxiliary space Θ(1)
When analyzing an algorithm that receives a number written in binary, what should the input-size variable n represent?
- A
The numerical value of the number
- B
The number of bits used to represent the number
- C
The number of arithmetic operations needed to read the number
- D
The number of possible values of the number
Consider this pseudocode: for i from 1 to n, execute an inner loop for j from 1 to i. What is the tight asymptotic running time?
- A
Θ(1)
- B
Θ(n)
- C
Θ(n²)
- D
Θ(log n)
True or false: An algorithm can be efficient or inefficient only after the underlying problem has been shown to be decidable.
- A
True
- B
False
An algorithm scans an array of n values and maintains only a fixed number of variables while it runs. What is the auxiliary-space complexity class?
A loop starts with n = 64 and repeatedly replaces n with floor(n / 2) while n > 1. How many iterations does it execute?
A simplified cost model assigns one unit to the initialization, one unit to each execution of the loop body, and one unit to the return statement. For the sum loop described in the material, with n = 8, what is the value of T(8)?
Related study packs and tools
AP Computer Science A: Integrated Java Problem Solving
A practical review of the integrated Java skills, debugging habits, algorithm reasoning, and free-response strategies needed for AP Computer Science A.
Fault Tolerance and Redundant Systems
A progressive guide to designing, operating, and testing systems that continue useful service despite component faults, overload, data loss, and recovery challenges.
How the Internet Works
A medium-difficulty quiz on how independently operated networks, protocols, addresses, naming systems, transport services, and routing mechanisms work together to form the Internet.
Java ArrayList and Collections: Operations, Traversals, and Algorithms
Learn how to create, modify, traverse, and analyze Java lists with ArrayList, wrapper types, standard algorithms, and the Collections utility class for AP Computer Science A.
Java Boolean Logic and Selection
Build a clear understanding of Java Boolean expressions, logical operators, selection statements, nested branching, equivalent logic, and systematic code tracing for AP Computer Science A.
Java Foundations and Program Design
A practical introduction to Java program structure, data types, operators, input and output, problem-solving strategy, testing, and debugging for AP Computer Science A.
Java Inheritance and Polymorphism
A practical guide to Java inheritance, constructor chaining, method overriding, polymorphism, access control, and object behavior for tracing and writing AP Computer Science A programs.
Java Objects, Classes, and the String API
A focused guide to Java classes, object references, constructors, methods, strings, wrapper classes, and API usage for AP Computer Science A.
Java Primitive Types and Expression Evaluation
A focused guide to Java primitive types, expression evaluation, numeric conversion, floating-point behavior, integer overflow, and common methods in the Math class for AP Computer Science A.
Java Primitive Types and Expressions
A focused review of Java primitive types, expression evaluation, numeric conversion, arithmetic behavior, Math methods, randomness, and tracing techniques for AP Computer Science A.
Packets, Links, and Network Performance
A progressive guide to how packet-switched networks encapsulate data, move it across links, and manage delay, throughput, queues, and congestion.
Parallel and Distributed Computing
A structured guide to designing parallel and distributed systems through decomposition, communication, coordination, state management, scalability, and fault tolerance.