programs A and B are analyzed and found to have worst-case running times no grea

Question

programs A and B are analyzed and found to have worst-case running times no greater than 150Nlong_2N and N^2, respectively. Answer the following questions, if possible

a. Which program has the better guarantee on the running time, for large values of N(N>10,000)?

b. Which program has the better guarantee on the running time, for small values of N(N<100)?

c. Which program will run faster on average for N = 1,000?

d. Is it possible the program B and will run faster than program A on all possible inputs?

Explanation / Answer

A-For this case B will have better guarantee for running time as it will execute faster . nlog2n will become larger for larger values of n as compared to 2n.

B-For this case A have better running time it will execute faster for n<100 2n will have larger values than nlog2n.

C-For this case A will have running low time as log2n=log1000×2=log 2000 =6.... now n×6=6n=6000....150×6000=900000

Whereas n×n=1000000

D- for very higher value of n it is possible....... For all possible inputs it can be possible

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.