What is the effect in the time required to solve a problem w

What is the effect in the time required to solve a problem when you double the size of the input from n to 2n, assuming that the number of milliseconds the algorithm uses to solve the problem with input size n is each of these function? [Express your answer in the simplest form possible, either as a ratio or a difference. Your answer may be a function of n or a constant.] log log n log n 100n n log n n^2 n^3 2^n

Solution

e) for n and 2n it is n² : n⁴

f) for n and 2n it is n³ : n⁹

g) for n and 2n it is 2ⁿ : 4²ⁿ

c) for n and 2n it is 100n:200n

b) for n and 2n it is log n : log ²ⁿ

d) for n and 2n it is n log n : n² log ²ⁿ

a) for n and 2n it is log log n: log log ²ⁿ

^{Asymptotically all these are corect but in terms of milliseconds just a 30% of time or above resulted in time increase.}