CSCI 2405
Spring 2018
Practice Questions for Exam 3

1. Suppose that

    f(n) ≈ 3T(n/2) + n

   Give a closed form expression for f(n) that is correct to within a constant factor.

   Answer

2. Suppose that

    f(n) ≈ 4T(n/2) + n²

   Give a closed form expression for f(n) that is correct to within a constant factor.

   Answer

3. Suppose that

    f(n) ≈ 3T(n/2) + n²

   Give a closed form expression for f(n) that is correct to within a constant factor.

   Answer

4. Suppose that {a_n} (n ≥ 0) is a sequence where, for n > 1,

    a_n = 5a_n−1 − 6a_n−2

   Give the general form of a closed-form solution for a_n.

   Answer

5. Suppose that {a_n} (n ≥ 0) is a sequence where, for n > 1,

    a_n = 4a_n−1 − 4a_n−2

   Give the general form of a closed-form solution for a_n.

   Answer

6. Suppose that {a_n} (n ≥ 0) is a sequence where, a₀ = 2 and, for n > 0,

    a_n = 3a_n−1

   Give an exact closed-form solution for a_n.

   Answer

7. Suppose that {a_n} (n ≥ 0) is a sequence where, a₀ = 2 and, for n > 0,

    a_n = 3a_n−1 + n

   Give an exact closed-form solution for a_n.

   Answer