Question

In: Computer Science

Suppose we run mergesort (T(n) ≈ nlogn) on a very slow computer and bubblesort (T(n) ≈...

Suppose we run mergesort (T(n) ≈ nlogn) on a very slow computer and bubblesort (T(n) ≈ n2) 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.)

Solutions

Expert Solution

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


Related Solutions

Suppose the runtime of a computer program is proportional to 2^n where n is the input...
Suppose the runtime of a computer program is proportional to 2^n where n is the input size. When given an input of size 1024, suppose the runtime is 256ms. For what input size would the program have runtime of 1ms? A program takes time proportional to the input size. If the program takes 36 milliseconds for input size 30, how  many milliseconds does it take for input size 10? A program takes time T(n) = k2n  where k is some constant and...
1. If a two-sided t- test is run and the t-stat=2.20, we definitely reject H0 at...
1. If a two-sided t- test is run and the t-stat=2.20, we definitely reject H0 at α=0.05 T/F 2. If we run a one-sample t-test and get a t-stat=6.74, with n=7, the p-value under one-sided conditions is: 3. For which of the following hypothetical scenarios is a binomial distribution most acceptable? a. Surveying former smokers and asking them whether or not they have emphysema. b. Finding out if there is a significant difference between the blood pressures of people who...
Exercise 2.5.1 Suppose T : R n ? R n is a linear transformation. Prove that...
Exercise 2.5.1 Suppose T : R n ? R n is a linear transformation. Prove that T is an isometry if and only if T(v) · T(w) = v · w. Recall that an isometry is a bijection that preserves distance.
Suppose a bacterial population at any given point in time is given by N(t). Suppose that...
Suppose a bacterial population at any given point in time is given by N(t). Suppose that it grows at 1.8 percent per hour. Construct differential equation to capture the population growth dynamics and present its definite solution. Suppose there are 10000 cells at time zero. How many cells will there be in 24 hours?
Suppose Amazon is considering the purchase of computer servers and network infrastructure to expand its very...
Suppose Amazon is considering the purchase of computer servers and network infrastructure to expand its very successful business offering​ cloud-based computing. In​ total, it will purchase $47.2 million in new equipment. This equipment will qualify for accelerated​ depreciation: 20% can be expensed​ immediately, followed by 32%​, 19.2%​, 11.52%​, 11.52%​, and 5.76% over the next five years.​ However, because of the​ firm's substantial loss carryforwards and other​ credits, Amazon estimates its marginal tax rate to be 10% over the next five​...
Suppose Amazon is considering the purchase of computer servers and network infrastructure to expand its very...
Suppose Amazon is considering the purchase of computer servers and network infrastructure to expand its very successful business offering​ cloud-based computing. In​ total, it will purchase $ 48.9$48.9 million in new equipment. This equipment will qualify for accelerated​ depreciation: 20 %20% can be expensed​ immediately, followed by 32 %32%​, 19.2 %19.2%​, 11.52 %11.52%​, 11.52 %11.52%​, and 5.76 %5.76% over the next five years.​ However, because of the​ firm's substantial loss carryforwards and other​ credits, Amazon estimates its marginal tax rate...
Usually, the sample size is small (n<30), we would use the t-distribution value. However, if we...
Usually, the sample size is small (n<30), we would use the t-distribution value. However, if we know the population standard deviation, we still use the z-distribution value even though the sample size is small. Describe what the reason that we use z-distribution if we know the population standard deviation.
n the New Keynesian model, suppose that in the short run the central bank cannot observe...
n the New Keynesian model, suppose that in the short run the central bank cannot observe aggregate output or the shocks that hit the economy. However, the central bank would like to come as close as possible to economic efficiency. That is, ideally the central bank would like the output gap to be zero. Suppose initially that the economy is in equilibrium with a zero output gap. (a) Suppose that there is a shift in money demand. That is, the...
Suppose that a market has n = 100 identical firms and that the market is in a short-run competitive equilibrium.
  Suppose that a market has n = 100 identical firms and that the market is in a short-run competitive equilibrium. All firms have the same total cost function TC(q) = q2. The market price is P = 10. As the market moves from the short-run equilibrium to the long-run equilibrium, a. the total market quantity of output decreases. b. the number of firms increases. c. the market price increases. d. the demand curve shifts to the left.
Suppose that a community contains 15,000 people who are susceptible to a contagious disease. If N(t)...
Suppose that a community contains 15,000 people who are susceptible to a contagious disease. If N(t) represents the number of people who have become infected in thousands, where t is time in days, and N′(t) is proportional to the product of the numbers of those who have caught the disease and of those who have not. The following logistic model can be used to model the spread of the disease. dN/dt= 1N(15−N) dt 100 (a) Sketch the phase line (portrait)...
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT