| How long it would take to sort... | ||||||||||
|
30 Day Risk-Free Guarantee:
100% money back if you're unsatisfied. Book (308 Pages):
 Video (One Hour):
 Resume Review (24 - 48hr)
All Products / Services
|
||||||||||
How long it would take to sort 1 billion numbers? make any assumptions you wanted.. assume the computer would have more than 4 GB of RAM, so the array would fit in memory in its entirety, and the machine would run at 4 GHz.
11
Long as in how many seconds/minutes/hours it would take. Not asking for big O notation here.
Can only roughly guess. 6.96 second?
nlogn/4GHZ=10^10*log(10^10)/(4*10^9)=25sec
I thought the way you had thought... since billion = 10^9 (not 10^10) it becomes 2.25 sec. which is hard to believe (:
But we only think the cpu speed, data transfer from memory to cpu and other operational stuff, will decrease the performance. Also we assume that cpu is not doing anything but our sorting operation.
4GB memory can not store 1billion numbers. So....
And why exactly not?
4 GB = 2^2 X 10 ^ 9
1 billion = 10 ^ 9
Assuming 1 integer is 4 bytes, 1 billion numbers take 4 GB memory. Also, the question says we have more than 4 GB available.
for me it comes to 7.5 sec...
nlogn/4GHZ (n=1 billion = 2^30 or 10^9 as per US...also 1G=2^30)
= [1024^3 * log( 1024^3)] / [4 * 1024^3]
= [2^30 * log(2^30)] / [4 * 2^30]
= [2^30 * 30] / [4 * 2^30]
= 30/4 = 7.5 sec
Can any one explain how all this is working here? I mean I'm confused with 4GHz, how do we count the fastness of a computer from its GHz? any layman's terms would be really appreciated :)
Hertz is a measure of electric cycles per second (as in, the electrical signal on an oscilloscope would complete one full cycle, from baseline, to peak, to baseline, to trough, to baseline). For processors, one calculation can be performed per cycle.
So...
1 HZ = 1 processor cycle (calculation) per second
Giga is the prefix that indicates billions, so
1 GHZ = 1 billion calculations per second
4 GHZ = 4 billion calculations per second
do you all really think that CPU has the same speed with memory and the cpu can access to memory immediately? and there is also RAM latency
it is just the cpu clock time. what about memory access, copy cache operations, they are the time consuming ones.
>>make any assumptions you wanted..
Khoa what if I assumed that numbers are already sorted, then i just need one pass thrugh 1 billion numbers to confirm that they are already sorted.
Anyways the above assumptions may not impress anybody so I believe if all the 1 billion numbers could fit in memory then i would go for any inplace O(nlogn) algorithm .. personal choice would be quick sort(randomized version) or even heap sort is also not a bad idea.
is this problem vague just to test the candidate as where he goes with assumptions ?
statistical info abt the data could really help in choosing abt the algorithm.