Prove tight worst-case asymptotic upper bounds for the following recurrence equations that satisfy T(x) = 1 for x ≤ 2, and depend on a variable y ∈ [0, x/4]

profileptn32

Note that you need to prove an upper bound that is true for every value of y ∈ [0, x/4] and a matching lower bound for a specific value of y ∈ [0, x/4] of your choosing. Do not assume that a specific y yields the worst case input; instead, use algebra to show what y maximizes the running time. Please be specific.

a) T(x) = T(x − 2y − 1) + T(3y/2) + T(y/2) + Θ(1)
b) T(x) = T(x − y − 1) + T(3y) + Θ(x)

    • 9 years ago
    • 15
    Answer(0)