Question

1.

a. In tilde notation, Heapsort's performance is ______________________ .

Select one:

a. quadratic

b. constant

c. linear

d. linearithmic

b. In tilde notation, Quicksort's performance is _____________________ .

Select one:

a. quadratic

b. linearithmic

c. linear

d. constant

c. shellsort's average performance is closest to ________________.

d. When comparing the elementary sorts, choose the correct ranking of performance

A < B means that A's time to sort is less than B's (i.e., A is faster than B)

Select one:

a. Insertion < selection < shellsort

b. none of the other choices

c. selection < shellsort < insertion

d. shellsort < insertion < selection

Answer 1

a. In tilde notation , ignores logarithmic factor . It is a variant of big - O.

As we know time complexity of Heapsort is O(nlogn) .

But in tilde notation it will perform in linear .

So option c .

b. Quick sort time complexity is O(n^2) . There are no logarithmic factor . So it will perform in quadratic time.

so option a .

c. shell sort's average performance is closet to O(n) .

and less than O(n^2).

for small and medium size array it is much fast than bubble and insertion sort.

D.

for an average size

time take by different sort is like.

shell sort < insertion < selection

mean shell sort take less time than insertion and insertion take less time than selection sort.

so option d .