Free Practice Quiz Question List

1 Algorithm Analysis and Big-O Notation Online Quiz Questions

Use this free practice quiz with 20 questions to review 1 Algorithm Analysis and Big-O Notation, test your knowledge, and prepare for your next test or exam.

20 questions

Fill in the blank

1 point

A stack removes items according to the rule.

True or false

1 point

An average-case complexity claim is meaningful only when the assumptions about the distribution of possible inputs are stated.

A
True
B
False

Choose all

1 point

Select all statements that correctly describe typical operation costs under the assumptions stated in the material.

A
Accessing an array element by index is typically $\Theta(1)$ .
B
Inserting near the beginning of an array can require $\Theta(n)$ shifting.
C
Random access in a linked list is typically $\Theta(1)$ .
D
Search in a balanced search tree is typically $\Theta(\log n)$ .
E
Traversing a linked list to find a position is always $\Theta(1)$ .

Open ended

1 point

You are choosing between an array and a linked list. The workload requires frequent indexed reads in one case and frequent insertions at positions whose node pointers are already known in another case. Explain which representation is better for each workload and justify the choice using typical time complexities.

True or false

1 point

If an algorithm has runtime $\Theta(f(n))$ , then it has both an $O(f(n))$ upper bound and an $\Omega(f(n))$ lower bound.

A
True
B
False

Choose one

1 point

Simplify the runtime expression $4n^2+3n+9$ using tight asymptotic notation.

A
$\Theta(1)$
B
$\Theta(n)$
C
$\Theta(n^2)$
D
$\Theta(n^3)$

Choose one

1 point

Which choice is an abstract data type rather than a concrete data structure?

A
A stack implemented with an array
B
The stack ADT specifying push, pop, and top
C
A linked list used to store stack nodes
D
A hash table used to implement lookup

Choose one

1 point

An algorithm has an outer loop that runs n times and, for every outer-loop iteration, an inner loop that also runs n times. What is the tight runtime complexity if the inner body takes constant time?

A
$\Theta(1)$
B
$\Theta(n)$
C
$\Theta(n^2)$
D
$\Theta(2^n)$

Choose one

1 point

A sequential search examines an unsorted array of n elements, and the target is guaranteed to be present at a uniformly random position. What is its average-case complexity?

A
$\Theta(n)$ under the stated uniform assumption
B
$\Theta(1)$ for every input
C
$\Theta(\log n)$ because the target is eventually found
D
$\Theta(n^2)$ because every pair of elements is compared

Choose one

1 point

Under which condition is a hash table's expected search, insertion, and deletion time commonly $\Theta(1)$ ?

A
The table is sorted, so binary search always applies
B
The load factor is irrelevant to lookup time
C
Hashing guarantees $\Theta(1)$ in every possible worst case
D
A suitable hash function and controlled load factor support expected $\Theta(1)$ operations

Choose one

1 point

A recursive algorithm reaches a maximum recursion depth of n, and each call stores only a constant amount of information. What is its auxiliary space complexity due to the call stack?

A
$\Theta(1)$ , because each call stores only constant information
B
$\Theta(n)$ , because the recursion depth is n
C
$\Theta(\log n)$ , because every recursive algorithm halves its input
D
$\Theta(n^2)$ , because the calls are nested

True or false

1 point

True or false: If an algorithm has tight runtime complexity $\Theta(n^2)$ , then it is also correct to describe it as $O(n^3)$ , although $O(n^2)$ is the tighter upper bound.

A
True
B
False

Written response

1 point

A divide-and-conquer algorithm satisfies $T(n)=2T(n/2)+\Theta(n)$ . Enter its tight runtime complexity in LaTeX.

Written response

1 point

What term describes the additional memory an algorithm uses beyond the memory required to store its input?

Choose one

1 point

One part of an algorithm takes $\Theta(n)$ time and a later part takes $\Theta(n^2)$ time. What is the tight complexity of the complete algorithm?

A
$\Theta(n)$
B
$\Theta(n\log n)$
C
$\Theta(n^2)$
D
$\Theta(n^3)$

Choose all

1 point

Select all statements that are supported by the stated data-structure complexity assumptions.

A
Search, insertion, and deletion in a balanced search tree are typically $\Theta(\log n)$ .
B
A hash table guarantees $\Theta(1)$ search time in the worst case, regardless of collisions.
C
A hash table commonly has expected $\Theta(1)$ operations with a suitable hash function and controlled load factor.
D
Direct random access in a linked list is typically $\Theta(1)$ .

Written response

1 point

A search procedure operates on a sorted array and discards half of the remaining elements after each comparison. What is its tight runtime complexity in terms of the array size $n$ ?

Written response

1 point

An algorithm performs one constant-time operation for each bit in the binary representation of a positive integer $x$ . What is its runtime expressed as a tight asymptotic function of $x$ ?

Fill in the blank

1 point

Complete the formal definition of an asymptotic upper bound: $T(n)$ is $O(f(n))$ if there are positive constants and such that $T(n) \le c \cdot f(n)$ for all $n \ge n_0$ .

Choose one

1 point

For sequential search in an array of $n$ elements, which pair correctly describes the best-case and worst-case runtimes?

A
Best case $\Theta(n)$ , worst case $\Theta(1)$
B
Best case $\Theta(1)$ , worst case $\Theta(n)$
C
Best case $\Theta(\log n)$ , worst case $\Theta(n)$
D
Best case $\Theta(1)$ , worst case $\Theta(\log n)$