3. Programming & Data Structures

Complexity Analysis — Quiz

Test your understanding of complexity analysis with 5 practice questions.

Practice Questions

Question 1

Given the recurrence relation $T(n)=3T(n/2)+n$, which of the following most accurately describes the asymptotic time complexity of $T(n)$?

Question 2

Which asymptotic notation provides a tight bound for an algorithm's running time, signifying that the function grows asymptotically neither faster nor slower than a reference function?

Question 3

An algorithm stores precomputed results in a table of size $n$ to reduce computation time from $O(n^2)$ to $O(n)$ at the cost of additional $O(n)$ space. Which concept does this illustrate?

Question 4

Consider a hash table that doubles its capacity when full. After $k$ insertions starting from empty, what is the amortized time complexity per insertion?

Question 5

If $f(n)=\Omega(n^2)$ for sufficiently large $n$, which statement must be true?