Too slow to sort

Computer Science Level 1

One day you decide to sort data on your old INTEL 8008 computer. If a mergesort algorithm in worst case takes 84 seconds to sort an input of size 256.

Which of the following closely approximates the maximum input size that can be sorted by the computer in a worst case runtime of 7 minutes?

4096 512 1024 2048

3 solutions

Eli Ross Staff
Oct 29, 2015

Note that the worst-case sort time for Mergesort is approximately proportional to $n\log_2(n).$

Note that 7 minutes is 5 times as long as 84 seconds. Thus, the maximum input size would be $n$ such that $n\log_2(n) = 5\cdot 256 \log_2(256) = 10240.$

Checking the choices, $1024\log_2(1024) = 10240,$ so 1024 is our answer.

I got it wrong, but got it right anyway! I got as far as 7 minutes is 5 times as long as 84 seconds, but then I just multiplied 256 x 5 = 1280. Since 1280 isn't one of the answers, but the question asked for an approximation, I just went with the answer closest to 1280.

As a 5th grade math teacher, I'm not up to speed on complicated math, but when it comes to multiple-choice tests, I spend my life teaching how to guess the right answer when you don't really know!

Nic Diamond - 5 years, 7 months ago

i thought the same but i thought that "in worst case it takes 84 sec to sort 256 , therefore in 7 min it will sort 1280 but since it is the max time taken by it to sort 256 SUPPOSE it become a little faster in between these 7 minutes and gain a sped of sorting of>256 in 84 second the it will sort >1280
and the are 2 such a answers 2048 and 4096 since 4096 is probably out of sight but it can sort 2048 that can be a answer

anshul sharma - 5 years, 1 month ago

Worst case is WORST case, if it goes just a bit faster then that is no longer the worst case.

Mark McClan - 1 year, 10 months ago

Nic, you did not get it wrong, you got it exactly right. This is a linear problem, logarithms have nothing to do with it.

Mark McClan - 1 year, 10 months ago

This is a linear problem, logarithms have nothing to do with it. Further, the question asks for an approximation. You state the sort time is "approximately proportional to n\log_2(n)", yet the answer obtained is an EXACT match by your theory...this should have been your first clue it was not correct. There is also nothing to infer the need to use BASE2...the max input size of 256 could be bits, Bytes or even the number of street addresses it can take as input /84 seconds.

Mark McClan - 1 year, 10 months ago

Sachin Kumar
Nov 29, 2015

As merge sort takes "nlog(n)" (log base 2) time to execute in worst case.
So
84 sec = 256*log(256) (remembering log base 2)
84 sec = 2048 (operation)
1 sec = 24.32
So the computer performs 24.32 tasks in one second.
In 7 minutes or 420 sec, the computer can perform
420 * 24.32 tasks ~= 10240 task
and 10240 = 1024 log (1024)

Thank you, this was better than the staff solution

Janac Meenachisundaram - 3 months, 1 week ago

Jacob Meek
Nov 3, 2015

1.4 min =84 sec

1.4/256=7/X

7*256=1855

1.4X=1855

x=1325

1024 is the closest to 1325

The runtime isn’t linear so you cannot compute proportions like this.

Karthik Halukurike - 3 years, 4 months ago

I know he has entered a miscalculation in his results, but can you please explain your reasoning as to how the runtime is not linear?

Mark McClan - 1 year, 10 months ago

Your formulation is correct, however... 7*256=1792, not 1855. Thus x=1280. You have accidentally entered 265 instead of 256 when you calculated.

Mark McClan - 1 year, 10 months ago

Too slow to sort

3 solutions

0 pending reports