2 Algorithm A performs 10n2 basic operations and algorith B

2. Algorithm A performs 10n^2 basic operations, and algorith B performs 300 In n basic operations. For what value of n does algorithm B starts to show its better performance?

Solution

1.) For the given condition count sort will be the best algorithm to sort n distinct integers in theta(n). Count sort uses a fix sized array to sort fixed no. of elements. Count sort can be given as:

a.) find the min and max from the given numbers; and define the range.

b.) count the occurence of frequency of each element in a separate array say count[]

c.) now, modify the values of count array to store cumulative frequencies of given elements in it.

d.) now using the above modified array count, it places the values in the correct order.

2.) for n >= 2⁸; algo. B will starts to show better performance over A but for n < 2⁸; algo. A will perform better than that of B.