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]
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)
other Questions(10)
- E-Commerce Security Plan
- Brilliant Answers
- s 2 + 49 s = 0
- PAD 520 ASSIGNMENT 4
- Question
- Response to paper
- I need this done within 12 hours. I am willing to pay for the rest of my school year. I need proof that this is not a prank and can be done.
- activity data set
- QNT 275 Statistics For Decision Making
- Racism and Privilege