3. Algorithms

Algorithm Analysis — Quiz

Test your understanding of algorithm analysis with 5 practice questions.

Practice Questions

Question 1

Consider the following pseudocode: for(i=1; i<=n; i++){ for(j=i; j<=n; j+=i){ /* constant work */ }} What is its time complexity?

Question 2

Given the recurrence $T(n)=3T(n/4)+n$, what is the asymptotic solution for $T(n)$?

Question 3

Algorithm A requires $n^2$ operations and algorithm B requires $100n$ operations. For which values of $n$ is B more efficient than A?

Question 4

Which sorting algorithm guarantees a worst-case time complexity of $O(n\log n)$ but requires $O(n)$ auxiliary space?

Question 5

What is the time complexity of the naive recursive Fibonacci function defined by $F(n)=F(n-1)+F(n-2)$ with constant-time additions?