# Question: Question 1: • Compare computers A and B that are running algorithms a and b. Algorithm a, takes time roughly equal to cynto sort n items, where C1 is a constant that does not depend on n. That is, it takes time roughly proportional to n?. In general, the code requires 4n2 instructions to sort n numbers. • Algorithm b, takes time roughly equal to canlgn, where Ign stands for log2 n and c2 is another constant that also does not depend on n. In general, the code requires 20nlgn instructions to sort n numbers. • Computer A executes 20 billion instructions per second and computer B executes 10 billion instructions per second. What is the time that it takes computers A and B to sort • 100 • 1000 • 10000 • 100000 • 1000000 numbers? – Free Chegg Question Answer

Transcribed text From Image:Question 1: • Compare computers A and B that are running algorithms a and b. Algorithm a, takes time roughly equal to cynto sort n items, where C1 is a constant that does not depend on n. That is, it takes time roughly proportional to n?. In general, the code requires 4n2 instructions to sort n numbers. • Algorithm b, takes time roughly equal to canlgn, where Ign stands for log2 n and c2 is another constant that also does not depend on n. In general, the code requires 20nlgn instructions to sort n numbers. • Computer A executes 20 billion instructions per second and computer B executes 10 billion instructions per second. What is the time that it takes computers A and B to sort • 100 • 1000 • 10000 • 100000 • 1000000 numbers?

## Expert Chegg Question Answer:

Answer:

## Answer

**Given Algorithms with Cost Function :**

- Algorithm a = 4n
^{2}# number of instructions to sort n numbers - Algorithm b = 20n(log
_{2}n) # number of instructions to sort n numbers - Time to sort n number by Computer A using an algorithm a = 4n
^{2}/ 20 *10^{9}seconds - Time to sort n number by Computer B using an algorithm b = 20n(log
_{2}n) / 10 *10^{9}seconds

**The Chart is given below with the total time taken by Computer A and B for sorting :**

Numbers to Sort | Algorithm a | Algorithm B | Computer A | Computer B |

100 | 40000 | 13287.7 | 2*10^{-6} sec | 1.3*10^{-6} sec |

1000 | 4000000 | 199315.6 | 2*10^{-4} sec | 1.99*10^{-5} sec |

10000 | 4 * 10^{8} | 2657542.4 | 0.02 sec | 2.25*10^{-4}sec |

100000 | 4 * 10^{10} | 33219280.9 | 2 sec | 3.32*10^{-3}sec |

1000000 | 4 * 10^{12} | 0.398*10^{9} | 200 sec | 0.0398sec |