Computers and Technology, 08.04.2020 01:45 deannajd03

We are going to derive an upper bound for the average number of exchanges for quicksort. A similar analysis would give a lower bound, giving the high order term exactly.

(a) Assume that the partition (or pivot) element ends up in position q. How many exchanges does partition do, NOT counting the final exchange where the pivot element is placed in its proper sorted position? Briefly justify. Note that an element can exchange with itself.

(b) Write a recurrence for the expected number of exchanges (for quicksort), NOT counting the final exchange where pivot element is placed in its proper sorted position.

(c) Simplify the recurrence as much as reasonably possible (as we did in class for comparisons).

(d) Guess that the solution is at most an In n for some constant a. Use constructive induction to verify the guess and derive the constant a.

(e) Give an upper bound on how many exchanges involve the pivot element thoughout all of the partitions in the entire quicksort algorithm. Briefly justify.

(f) Add this value to your answer in Part (d) to get an upper bound on the total number of exchanges.

(g) Rewrite your solution using log base 2 rather than the natural log, evaluating the constant to three decimal places.

Answers: 1

Show answers

Another question on Computers and Technology

Computers and Technology, 22.06.2019 15:30

When creating a budget, log fixed expenses before income. after income. after savings. at the top.

Answers: 1

Answer

Computers and Technology, 22.06.2019 20:40

Assume that there is a 4% rate of disk drive failure in a year. a. if all your computer data is stored on a hard disk drive with a copy stored on a second hard disk drive, what is the probability that during a year, you can avoid catastrophe with at least one working drive? b. if copies of all your computer data are stored on three independent hard disk drives, what is the probability that during a year, you can avoid catastrophe with at least one working drive?

Answers: 1

Answer

Computers and Technology, 22.06.2019 21:00

Write a method so that the main() code below can be replaced by the simpler code that calls method original main(): public class calcmiles { public static void main(string [] args) { double milesperhour; double minutestraveled; double hourstraveled; double milestraveled; milesprhour = scnr.nextdouble(); minutestraveled = scnr.nextdouble(); hourstraveled = minutestraveled / 60.0; milestraveled = hourstraveled * milesperhour; system.out.println("miles: " + milestraveled); } }

Answers: 2

Answer

Computers and Technology, 23.06.2019 11:00

What are the possible consequences of computer hacking? what is computer piracy? describe some examples. what are the effects of computer piracy? what are the possible consequences of computer piracy? what is intentional virus setting? describe some examples. what are the effects of intentional virus setting? what are the possible consequences of intentional virus setting? what is invasion of privacy? describe some examples. what are the effects of invasion of privacy? what are the possible consequences of invasion of privacy? what is an acceptable use policy and what is the purpose of the acceptable use policy what is intellectual property and how can you use it?

Answers: 1

Answer

You know the right answer?

We are going to derive an upper bound for the average number of exchanges for quicksort. A similar a...

Questions