Question

Suppose we run mergesort (T(n) ≈ nlogn) on a very slow computer and bubblesort (T(n) ≈ n²) on a fast computer so it happens that the two programs take the same amount of time to sort an array of size 100.  Next we do the same experiment, except this time the array size is increased to (10) ^ 4 for both algorithms. What is the expected ratio of the new runtimes (bubblesort time divided by mergesort time) ?

(Type your answer rounded to 1 digit after the decimal point, if it's not a whole number.)

Answer 1

Merge sort : T(n) = n logn

Bubble sort: T(n) = n^2

Now for input 100:

Merge sort has operations:

T(100) = 100 log(100) = 100 x 2 = 200

Buuble sort has operations:

T(100) = 100^2 = 10000

Let's both take t time.

For the slow computer 1 operation takes t/200 time.

For the fast computer 1 operation takes t/10000 time.

So (t/10000) / (t/200 ) = .02

So bubble : merge in same computer = 1/0.02 = 50

Now the size of the array is 10^4

Merge sort has operations:

T(10^4) = 10^4 log(10^4) = 4 x 10^4

Buuble sort has operations:

T(10^4) = 10^4 = 10^8

Let slow computer takes t1 time and fast computer takes t2 time for this operation.

1 operation takes in slow computer = t1/(4 x 10^4)

1 operation takes in fast computer = t2/(10^8)

so ratio:

(t2/(10^8)) / (t1/(4 x 10^4)) = (t2 x 4 x 10^4/t1 x 10 ^ 8)

Now t2 = 50 x t1

After substituting we get

(t2 x 4 x 10^4/t1 x 10 ^ 8) = (50 x t1 x 4 x 10^4) / (t1 x 10 ^ 8) = 0.0002

So bubble : merge in same computer = 1/0.0002 = 5000