4. Suppose you record the run times of program P. You find out that on inputs of

Question

4. Suppose you record the run times of program P. You find out that on inputs of length 1, its run time is always 1/8 second, and on inputs of length 10, its run time is always 1/4 second. Under each of the following assumptions, calculate how long it will take to run the program on inputs of length 20, 100, 1000, and 10,000: (a) For some constants a and b (the values of which you must determine), running the program on a data set of size d always takes ad + b seconds. (b) For some constants a and b, running the program on a data set of size d always takes ad^2 + b seconds.

Explanation / Answer

a) From the two given details we get

a*1+b=0.125 and a*10 +b =0.25

Therefore, on subtracting the two equations we get,

9*a=0.125

=> a=1/72

=>b=1/9

Therefore running the program for 20,100,1000 and 10,000 length will take

0.389,1.5,14 and 139 respectively

b) From the two given details we get

a+b=0.125 and 100a+b =0.25

Therefore, on subtracting the two equations we get,

99*a=0.125

a=1/792

Therefore b= 0.1237

Therefore running the program for 20,100,1000 and 10,000 length will take

0.629, 12.75, 1262.75 and 126262.75 respectively

Related Questions

Navigate

• Browse (All)
• Browse 4
• Subjects

---

---

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