Tilde notation is more precise than Big-Oh notation at describing the growth of

Question

Tilde notation is more precise than Big-Oh notation at describing the growth of a function because:

I. Tilde notation includes the coefficient of the highest order term.

II. Tilde notation provides both an upper bound and a lower bound on the growth of a function.

III. Big-Oh notation suppresses lower order terms, so it does not necessarily accurately describe the behavior of a function for small values of N. Choose the best answer.

(a) I only.

(b) I and II only.

(c) I and III only.

(d) I, II and III.

(e) None.

Also please explain why, I want to learn this not just get the answer. Thanks <3

Explanation / Answer

Tilde Vs Big-Oh notation:

I) Tilde notation includes the coefficient of the highest order term. But the Big-O notation supresses the leading constant (coefficient)

For example, for the expression 20N2

II) Big-Oh gives an upper bound in describing order of growth of an algorithm. But Big-oh can’t give a lower bound. Whereas, tilde notation can give lower bound and upper bound.

III) Tilde notation supresses the lower ordered terms only when N is large(as N grows). But, Big-oh supresses the lower order terms and cannot describe the behaviour of a function for small values of N.

Therefore the correct answer is (d) I, II and III.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

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