Free Practice Quiz Question List

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.

20 questions

Choose one

1 point

When analyzing an algorithm that sorts a collection of records, what is the most appropriate interpretation of the input-size variable $n$ ?

A
The number of processor cores available
B
The number of records being sorted
C
The numerical value of the largest record
D
The number of programming languages used

Choose one

1 point

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(\log n)$
C
$O(n)$
D
$O(n^2)$

Choose one

1 point

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(\log n)$
C
$O(n^2)$
D
$O(2^n)$

Choose all

1 point

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.

Choose all

1 point

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

1 point

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

1 point

True or false: A loop that repeatedly replaces its remaining problem size with $\lfloor n/2\rfloor$ has $O(\log n)$ time complexity.

A
True
B
False

Written response

1 point

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.

Fill in the blank

1 point

Complete the statements: The resource measure for computational work is , while the resource measure for memory use is .

Fill in the blank

1 point

Complete the statement: The dominant growth class of $T(n)=4n^2+7n+12$ is .

Open ended

1 point

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.

Choose one

1 point

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
$\Theta(n)$
B
$\Theta(n^2)$
C
$\Theta(n\log n)$
D
$\Theta(2^n)$

Choose one

1 point

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(\log n)$
D
$O(n^2)$

Choose one

1 point

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 $\Theta(n)$ and auxiliary space $\Theta(n)$
B
Worst-case time $\Theta(n^2)$ and auxiliary space $\Theta(n)$
C
Worst-case time $\Theta(n^2)$ and auxiliary space $\Theta(1)$
D
Worst-case time $\Theta(2^n)$ and auxiliary space $\Theta(1)$

Choose one

1 point

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

Choose one

1 point

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

1 point

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

Written response

1 point

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?

Written response

1 point

A loop starts with n = 64 and repeatedly replaces n with floor(n / 2) while n > 1. How many iterations does it execute?

Written response

1 point

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)?