An algorithm requires $C(n)=30*n^3\sqrt[\phantom{2}]{n}$ basic operations to solve a problem with an input array of size $n.$

You first run the algorithm for an array of size $1000,$ and then for an array of size $10,000,$ on the same

computer.

$($a$)$ How many times longer will it run? Calculate $T\frac{10,000}{T}(1,000).$

Hint: Since we use the same computer, cop will simplify out!

$($b$)$ You are considering using a supercomputer that runs $1000$ times faster than the current one. How much

larger is the array that can be solved on the supercomputer in the same amount of time as on the old

computer?

Hints:

If the supercomputer is $1000$ times faster than the old, we have $c_{op1}=1000c_{op2}.$

For the old computer we have $T(n)=C_{op1}C(n).$ For the new computer, denote by $N$ the new array

size. We have and $T(N)=C_{op2}C(N).$

Since the times are equal, the ratio $T\frac{N}{T}(n)$ should equal $1.$ What does this say about the ratio

$\frac{N}{n}?($Algebra required!$)$

Work: