3. A certain linear algorithm takes 2 seconds to process with an input size of n=1000...

Transcribed Image Text:

3. A certain linear algorithm takes 2 seconds to process with an input size of n=1000 on an old desktop PC. a) How long would it take if n=2000? b) How long would it take for n=2000 if the algorithm were O(n) instead of linear? 4. A programmer is writing a binary search algorithm for use on an ordered array that will range in size from 1,000,000 to 10,000,000 records. a) What is the number of comparisons done in the worst case? b) What is the number of comparisons done in the best case? 3. A certain linear algorithm takes 2 seconds to process with an input size of n=1000 on an old desktop PC. a) How long would it take if n=2000? b) How long would it take for n=2000 if the algorithm were O(n) instead of linear? 4. A programmer is writing a binary search algorithm for use on an ordered array that will range in size from 1,000,000 to 10,000,000 records. a) What is the number of comparisons done in the worst case? b) What is the number of comparisons done in the best case?