Three students wrote algorithm for the same problem. They tested the three algor

Question

Three students wrote algorithm for the same problem. They tested the three algorithms with two sets of data as shown below:
A. case 1: n=10
Run time for student 1:1
Run time for student 2:1/100
Run time for student 3:1/1000
B. case 2:n=100
Run time for student 1:10
Run time for student 2:1
Run tme for student 3:1
C. case 3: n=1000
Run time for student 1:100
Run time for student 2: 100
Run time for student 3: 1000
For each algorithm dtermine the function that extrapolate its efficiency (extrapolation is the process of obtaining a value from a chart or graph that extends beyond the given dat). For example, efficiency for the algorithm can be presented as f1=1/10 *n. Which algorithm is the best? Which is the worst? Explain your answer.

Explanation / Answer

Clearly, For student 1, f(1) = n * 1/10 For student 2, f(2) = n^2 * 1/10,000 For student 3, f(3) = n^3* 1/1,000,000 These extrapolations can be derived by using trial and error so that all cases fit the formulae. As the input size (n) goes on increasing, the algorithm developed by student 1 will be the fastest, since growth rate is the least (linear). So, it is the best. As input size increases, the algorithm developed by student 3 will be the slowest since the run-time increase cubically. Thus, it is the worst.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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