Question

What is the effect in the time required to solve a prob- lem 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 pos- sible, either as a ratio or a difference. Your answer may be a function of n or a constant.]
A. log n
B. log log n
C. 100 n
D. n log n
E. n2
F. n3
G. 2n

Answer 1

Answer:

f(2n)-f(n)=log2

b.lg(lg2+lgn)-lglgn

c. f(2n)/f(n)=2

d.2nlg2+nlgn

e.f(2n)/(n)=4

f.f(2n)/f(n)=8

g. f(2n)/f(n)=2

Step-by-step explanation:

What is the effect in the time required to solve a prob- lem 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 pos- sible, either as a ratio or a difference. Your answer may be a function of n or a constant.]

from a

f(n)=logn

f(2n)=lg(2n)

f(2n)-f(n)=log2n-logn

lo(2*n)=lg2+lgn-lgn

f(2n)-f(n)=lg2+lgn-lgn

f(2n)-f(n)=log2

2.f(n)=lglgn

F(2n)=lglg2n

f(2n)-f(n)=lglg2n-lglgn

lg2n=lg2+lgn

lg(lg2+lgn)-lglgn

3.f(n)=100n

f(2n)=100(2n)

f(2n)/f(n)=200n/100n

f(2n)/f(n)=2

the time will double

4.f(n)=nlgn

f(2n)=2nlg2n

f(2n)-f(n)=2nlg2n-nlgn

f(2n)-f(n)=2n(lg2+lgn)-nlgn

2nLg2+2nlgn-nlgn

2nlg2+nlgn

5.we shall look for the ratio

f(n)=n^2

f(2n)=2n^2

f(2n)/(n)=2n^2/n^2

f(2n)/(n)=4n^2/n^2

f(2n)/(n)=4

the time will be times 4 the initial tiote tat ratio are used because it will be easier to calculate and compare

6.n^3

f(n)=n^3

f(2n)=(2n)^3

f(2n)/f(n)=(2n)^3/n^3

f(2n)/f(n)=8

the ratio will be times 8 the initial

7.2n

f(n)=2n

f(2n)=2(2n)

f(2n)/f(n)=2(2n)/2n

f(2n)/f(n)=2