Question

Two versions of a strategy to solve the “10 largest trades on a given day in the NYSE” problem are given below:

Strategy a: Updating an unsorted output array:

         a.1. Let B be an array of size 10.

         a.2. Copy the first 10 trade values from A into B.

         a.3. Scan B to locate the smallest trade value L in it.

         a.4. Repeat steps a.4.1-a.4.3for each of the remaining (10 million ─ten) trade values in A:

                   a.4.1 Get the next trade value from A and compare it with L.

                   a.4.2 If L is larger or equal, do nothing

                   a.4.3 Otherwise

                            a.4.3.1 Replace L in B with this next trade value from A.

                            a.4.3 2 Scan B to locate the smallest trade value L in it.

         a.5 Output the trade values in B.

The second version maintains B in a sorted state so that the largest trade value in it could be directly located:

Strategy a’: Updating a sorted output array:

         a’.1. Let B be an array of size 10.

         a’.2. Copy the first 10 trade values from A into B.

         a’.3. sort B in ascending or descending order

         a’.4. Repeat steps 3b.4.1-3b.4.2for each of the remaining (10 million ─ten) trade values in A:

                   a’.4.1 Get the next trade value from A and compare it with the smallest value in B

                   a’.4.2 If the smallest value in B is larger or equal, do nothing

                   a’.4.3 Otherwise

                            a’.4.3.1 Replace the smallest value in B with this next trade value from A.

                            a’.4.3 2 sort B in the same order

         a’.4. Output the trade values in B.

Which version is more efficient? Circle one:         

Strategy a        Strategy a’      both are equally efficient

Provide a technical justification or argument (short and precise) to support your claim:

Answer 1

For strategy a.

As the size of the B array is 10,so step 3 will take O(10) complexity.which is constant.

In step 4,In worst case ,let's assume ,each time we have to replace the L with the current number from A array.

The size of Array A is 10 million,so we'll have to replace L each time in worst case and searching the number in array B take O(10) time.so total time complexity is O(10*(10 million)).

For strategy a'.

As the size of the B array is 10.If we assume sorting takes O(n(logn)) then step 3 will take O(10*log10) complexity.which is constant.

In step 4,In worst case ,let's assume ,each time we have to replace the L with the current number from A array.

The size of Array A is 10 million,so we'll have to replace L each time in worst case and searching the number in array B take O(1) time because in sorted array in increasing order always presents at first index then sorting takes O(10log10).so total time complexity is O(10log(10)*(10 million)).

So it's obvious that 10 < (10log10) so strategy a is more efficiently.