4. A certain linear desktop PC r algorithm takes 2 seconds to process with an in

Question

4. A certain linear desktop PC r algorithm takes 2 seconds to process with an input size of -1000 on an old a) How long would it take if n-2000? b) How long would it take for-2000 if the algorithm were 0(r) instead of linear? c) How long would it take for n-2000 if the algorithm were O(r) instead of linear? 5. A programmer plans to use a sort algorithm known to be O(n). The project manager states that the algorithm is OK if it will sort 2,000 records in less than one second on the target machine. The programmer does a simple test, and finds that it takes 10 milliseconds to sort 100 records Is the algorithm fast enough? 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 6. a) What is the number of comparisons done in the worst case? b) What is the number of comparisons done in the best case? 234

Explanation / Answer

Hi, I have answered Q1. Please repost others in separate post

for n = 1000 it takes 2 sec

a) for n = 2000 , it takes = 2 * 1000 = 4 sec

b) if it is of n^2 (means (1000)^2 = 2 sec) then it takes (2*1000)^2 => 4 * (1000)^2 => 4*2 = 8 sec

c) if it is of n^3 (means (1000)^3 = 2 sec) then it takes (2*1000)^3 => 8 * (1000)^2 => 8*2 = 16 sec

Related Questions

Navigate

• Browse (All)
• Browse 4
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.