3 Suppose three algorithms are run on a machine that can exe

3. Suppose three algorithms are run on a machine that can execute one instruction every microsecond (10-6 seconds). They require, respectively, n log2(n), n log2(n)+5n, and n2 operations for a data set of size n. Compare the time the algorithms require for data sets of size a) 100 b) 100,000 c) 100,000,000

Solution

a) Three machines requires respectively: nlog₂(n) ,nlog2(n)+5n,n² operations for a data set of size n.

                       if n=100

            100log₂(100) ,100log2(100)+5(100), 100²

            100(6.64), 100(5.29)+500, 10,000

              664, 529+500, 10,000

           664, 1029, 10,000 (in micro seconds)

b) if n=1,00,000

                  100,000log₂(100,000) ,100,000log2(100,000)+5(100,000), 100000²

                           100,000(16.60) , 100,000(12.20)+(500,000), 10000000000

                   1660000,1220000+500,000, 10000000000

                 1660000,1720,000, 10000000000  

                   1.6 sec,1.72sec 10,000 sec

c) if n=1,00,000,000

                  100,000,000log₂(100,000,000) ,100,000,000log2(100,000,000)+5(100,000,000), 100,000,000²

                           100,000,000(26.57) ,100,000,000log2(100,000,000)+5(100,000,000), 100,000,000²

                            100,000,000(26.57) ,100,000,000(19.11)+5(100,000,000), 100,000,000²

                            2657000000,2411382792.4512310781561163758933, 100,000,000² microseconds