09-21-2018, 10:10 PM

Why is the answer to question number 7 not Case 1?

The equation is T(n) = 9T(n/4) + (n^2)logn

This means that the runtime of work at a level is n^(~1.585) which is the log (base 4) of 9.

If we compare their run times then n^(1.585) < (n^2)log(n)

This means that since the recursion has a higher growth rate, it contributes more work.

So why isn't it case 1?

The equation is T(n) = 9T(n/4) + (n^2)logn

This means that the runtime of work at a level is n^(~1.585) which is the log (base 4) of 9.

If we compare their run times then n^(1.585) < (n^2)log(n)

This means that since the recursion has a higher growth rate, it contributes more work.

So why isn't it case 1?