Algorithm A has runtime proportional to the square of the in

Algorithm A has runtime proportional to the square of the input size (\"quadratic time\") and algorithm B has runtime proportional to the log of the input size. A and B are first run with input size 100 and happen to take 1 second each. Now A and B are run for input size 10,000. What is the ratio of the new runtime for A to the new runtime for B? Show work.

Solution

Let, R and S denote runtimes of A and B

R=an^2

S=b log(n)

R(100)=1=a(100)^2

S(100)=1=b log(100)=2 b

So,

a(100)^2=2b

a/b=2/100^2

R(10000)=a(10000)^2

S(10000)=b log(10000)=4b

So,R(10000)/S(10000)=(a/b)*((10000)^2/(4))=(2/100^2)*((10000)^2/4)=5000