Question

Suppose you have algorithms with the five running times listed below.

(Assume these are the exact running times.)

How much slower (i.e., you need check the ratio) do each of these algorithms get when
you (a) double the input size, (b) increase the input size by one?

5nlog(n)

Answer 1

Required ratio = Performance of new time / performance of old time

We know that performance is inversely proportional to execution time

So, required ratio = execution time of old / execution time of new

a).Double the input size

Required ratio = old time / new Time = 5nlogn / (5*2nlog(2n))

= 5nlogn /10nlog2n

= logn / (2log2 + 2logn)

So, required slowdown or ratio in terms of n = logn/(2log2 + 2logn)

if we try to simply above then

ratio= 1/(2log2/logn + 2)

Suppose n tends to infinity then logn ->infinity so, log2 / logn = log2/infinity = 0

So, if n tends to infinity then ratio = 1/(0+ 2) = 0.5

b). Increase the input size by 1

Required slowdown or ratio = old time/new time

= 5(n+1)log(n+1)/5nlogn

= (n+1)log(n+1)/nlogn

So, required slowdown or ratio in terms of n = (n+1)log(n+1)/nlogn

Now , if we try to reduce above obtained ratio,we get

Ratio= (1+1/n)log(n(1+1/n))/logn

= (1+1/n)*(logn + log(1+1/n)) / logn

Suppose n tends to infinity then 1/n tends to 0

So, ratio = logn / logn = 1

So, if n is very large then by increasing input size by 1 the slowdown is almost negligible.