Tilde notation is more precise than Big-Oh notation at describing the growth of
ID: 3759013 • Letter: T
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.