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

A divide-and-conquer algorithm creates one recursive call on ⌈n/3⌉\lceil n/3 \rceil⌈n/3⌉ elements and another on ⌊2n/3⌋\lfloor 2n/3 \rfloor⌊2n/3⌋ elements, plus linear time to combine: T(n)=T(⌈n/3⌉)+T(⌊2n/3⌋)+nT(n) = T(\lceil n/3 \rceil) + T(\lfloor 2n/3 \rfloor) + nT(n)=T(⌈n/3⌉)+T(⌊2n/3⌋)+n Using the Akra–Bazzi theorem, we need to find ppp satisfying (1/3)p+(2/3)p=1(1/3)^p + (2/3)^p = 1(1/3)p+(2/3)p=1. Which value of ppp solves this?