7. Recurrence Relations
Applications To Algorithmic Thinking — Quiz
Test your understanding of applications to algorithmic thinking with 5 practice questions.
Practice Questions
Question 1
In algorithm analysis, what does a recurrence relation usually describe?
Question 2
Why is a base case necessary in a recurrence relation that models an algorithm?
Question 3
An algorithm solves a problem of size $n$ by first solving one problem of size $n-1$ and then doing $1$ extra unit of work. Which recurrence models this behavior?
Question 4
Suppose $T(1)=4$ and $T(n)=T(n-1)+3$ for $n>1$. What is $T(3)$?
Question 5
Which recurrence best matches the running time of merge sort on input size $n$?