Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
Test #2, Question 7
#1
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?
Reply
#2
You have it backwards. The work at the level is n^2 log n, not n^1.585.

n^2 grows faster than n^1,585

n^2 log n grows even faster, so case 3. An epsilon of .1 would work.
Reply
#3
(09-22-2018, 12:09 AM)lusth Wrote: You have it backwards. The work at the level is n^2 log n, not n^1.585.

n^2 grows faster than n^1,585

n^2 log n grows even faster, so case 3. An epsilon of .1 would work.

So the first expression is the work by the recursion and the second is the work done at a level?
Reply
#4
The term that references T on the right hand side is the work done by the recursion.
Reply


Forum Jump:


Users browsing this thread: 1 Guest(s)