Guest Session: 1 Question Remaining. Create Account to save progress.
Login
Recursionhard
0:00.0

A recursive algorithm makes 3 disjoint recursive calls on subproblems of sizes n/4n/4n/4, n/4n/4n/4, and n/2n/2n/2, and takes Θ(n2)\Theta(n^2)Θ(n2) time to combine results. The recurrence is T(n)=2T(n/4)+T(n/2)+n2T(n) = 2T(n/4) + T(n/2) + n^2T(n)=2T(n/4)+T(n/2)+n2. Using the Akra–Bazzi method, what is Θ(T(n))\Theta(T(n))Θ(T(n))? (Hint: Find ppp such that 2(1/4)p+(1/2)p=12(1/4)^p + (1/2)^p = 12(1/4)p+(1/2)p=1.)