Question

Suppose the runtime of a computer program is proportional to n(logn)². For input size 28 the runtime is 154 ms. What is the new runtime in ms when the input size is squared? (Type just the number, not "ms")

Answer 1

Solution:

Given,

=>Runtime is proportional to n(logn)^2

=>When n = 28, runtime = 154 ms

The answer will be "17,248"

Explanation:

=>Let say runtime = t

=>t n(logn)^2

=>t = c*n(logn)^2 where c is proportionality constant.

Finding value of c:

=>We know that when n = 28 , t = 154

Put n = 28 and t = 154

=>154 = c*28*(log28)^2

Assuming base of log 10(by default)

=>c = 154/(28*(log28)^2)

Now finding runtime(t) when n = (28)^2:

=>t = c*(28)^2*(log(28)^2)^2

=>t = {154/(28*(log28)^2)}*(28)^2*(2log(28))^2 using log property

=>t = {154/(28*(log28)^2)}*(28)^2*4*(log28)^2

Cancelling (log28)^2 and 28 from numerator and denominator

=>t = 154*28*4 ms

=>t = 17,248 ms

I have explained each and every part with the help of statements attached to the answer above.