Question 3: (6 marks) Although big-O notation determines a growth rate of a func

Question

Question 3: (6 marks) Although big-O notation determines a growth rate of a function, sometimes a worse algorithm may outperform a better algorithm for very small input sizes n. Consider each of the following big-O estimates f(n) for algorithm A and g(n) for algorithm B, all of which g(n) O((. For each instance of f and g, find the smallest integer input n beyond which, algorithm B will always outperform algorithm A. Show your work. For this question, you may use algebra, a graphing calculator or online resources to justify your answer. a) b) c) g(n)= 4x1082(n) g(n) = 100 × n × log2(n) g(n) = 6 × ns f(n)2 f(n) = f(n) = n6

Explanation / Answer

a) For better performance g(n) must be less f(n)

Hence 4*log2(n) < n/2

i.e, log2(n) < n/8

n < 2(n/8)

By trail and error we can easily find that 44 is the smallest integer that satisfies the above equation

Substituting 44 we get 44<45.254834,which satisfies the equation

b) 100*n*log2(n) < n2

100*log2(n) < n

n < 2(n/100)

we can clearly observe that 1000 satisfies this equation. Again by trail and error if we slowly decrease the values, 997 is the smallest integer that satisfies this equation

Substituting 997 gives 997 < 2(9.97) i.e, 997 < 1002.926385

c) 6*n5 < n6

i.e, 6 < n

which clearly is 7

  

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

---

---

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