Skills101
← All practice quizzes

Quiz: Recurrence Relations

5 questionsNo time limitPass: 60%+10 XP on first pass

Model problems with recurrences (Fibonacci, Tower of Hanoi, tiling, binary strings), solve linear homogeneous recurrences with the characteristic equation, handle non-homogeneous ones, and analyse divide-and-conquer algorithms with the Master Theorem — all checked in Python.

Log in to take the quiz

Free account · see your score, answers and explanations, earn XP

  1. Question 1

    What is the recurrence for the minimum number of Tower of Hanoi moves?

  2. Question 2

    How many binary strings of length 5 have no two consecutive 1s (from the demo)?

  3. Question 3

    What is the closed form of a(n) = 5a(n−1) − 6a(n−2) with a(0) = 1, a(1) = 4?

  4. Question 4

    By the Master Theorem, what is T(n) = 2T(n/2) + Θ(n)?

  5. Question 5

    What is T(n) = 8T(n/2) + Θ(n²)?