Find the worst-case runtime of this incorrect algorithm

Assignment Help Computer Engineering

Reference no: EM1327953

Part (A) Sort the array 15 80 35 25 60 30 into descending order using

a) the selection sort.
b) the buble sort.

Part (B) A first year student attempted to write mergesort in pseudocode as follows.

mergesort(theArray, n) {

if (n > 1){ // more than one item to sort

mergesort(left half of theArray, n/2)

mergesort(right half of theArray, n/2)

}

a) The above algorithm has a fundamental flaw. As written, how does it change theArray?

b) What is the worst-case runtime of this incorrect algorithm? Give as tight an asymptotic upper bound as possible, using Big-Oh notation as a function of n. Justify your answer.

The original course website where the problem comes from is here, I think it will be helpful if you take a look at it first: www.student.math.uwaterloo.ca/~cs134

Reference no: EM1327953

Questions Cloud

Find out present value : Find out present value of $300 received at the beginning of each year for 5 years? Suppose that the first payment is not received until the beginning of the third year.

Explain important information about e-business initiative : Explain Important information about E-business Initiative and describe the need for this initiative in terms of costs and benefits

Develop a graphical taxonomy : Develop a graphical taxonomy of the different health care technologies using Microsoft Excel.

Explain the operational components of planning : Describe the operational components of planning, sourcing, making, and delivering

Find the worst-case runtime of this incorrect algorithm : What is the worst-case runtime of this incorrect algorithm? supply as tight an asymptotic upper bound as possible, using Big-Oh notation as a function of n. Justify your answer.

Find out the income elasticity of demand : Find out the income elasticity of demand. Elucidate whether gas is a normal or inferior product.

Explain the five categories of primary revenue models : Explain the five categories of primary revenue models and explain why the selected company fits the category in which you placed it

Benefits and challenges while working in group : What were some benefits and challenges you faced while working in this group?

The greatest impact on the health care utilization pattern : Determine one (1) important factor that has had the greatest impact on the health care utilization pattern(s).

User Account

All Pages