CareerCup

options are
100
1000
2500
5000

Seems like 5k is an estimate. If you estimate the sqrt of 1/2 is 0.5, then 5k is the closest answer.

7k is right answer

@hraday
7K ,not in option but 7k is closest.(or we shuld say max Entries).

100/10000=50/x
ans 5000

So where do you get these numbers?

Bubble sort as we know has O(n^2) worst case performance and O(n) best case (when data are already sorted).

Consider the following extreme scenarios:

a) In the first run data were sorted so bubble sort run in O(n) time, that is, it did 10000 operations in 100 seconds or 100 ops per second. Now assume in second run data were sorted in reverse order so bubble sort run in O(n^2) time. With 100 ops per second it did 5000 ops, enough only to sort sqrt(5000) ~= 70 elements.

b) In the first run data were sorted in reverse order, so bubble sort took O(n^2) time, that means 10.000^2 = 100.000.000 ops or 1.000.000 ops per second. Assume the data are sorted in the second run, now bubble sort, in 50 sec, can process 50.000.000 elements.

Don't pay attention at the exact numbers, I'm talking about orders of magnitude, and it varies a lot.

I see what you're saying. We must have a different picture of what exactly constitutes a bubble sort. The way I learned to do it, way back in the day, has the best, worst, and average case at O(n^2). Insertion sort, on the other hand, can be as bad as O(n^2) or as good as O(n).