1answer.
Ask question
Login Signup
Ask question
All categories
  • English
  • Mathematics
  • Social Studies
  • Business
  • History
  • Health
  • Geography
  • Biology
  • Physics
  • Chemistry
  • Computers and Technology
  • Arts
  • World Languages
  • Spanish
  • French
  • German
  • Advanced Placement (AP)
  • SAT
  • Medicine
  • Law
  • Engineering
jenyasd209 [6]
3 years ago
13

Write down a recurrence relation for this version of QuickSort, and solve it asymp-totically. Show your work. Assume that the ti

me it takes to find the pivot (eitherbest or worst, depending on the level of recursion) is Θ(n) for lists of lengthn.
Computers and Technology
1 answer:
torisob [31]3 years ago
5 0

Answer:As in merge sort, the time for a given recursive call on an n-element subarray is Θ(n). In merge sort, that was the time for merging, but in quicksort it's the time for partitioning.

Explanation:

Worst-case running time:

When quicksort always has the most unbalanced partitions possible, then the original call takes cncnc, n time for some constant ccc, the recursive call on n-1n−1n, minus, 1 elements takes c(n-1)c(n−1)c, left parenthesis, n, minus, 1, right parenthesis time, the recursive call on n-2n−2n, minus, 2 elements takes c(n-2)c(n−2)c, left parenthesis, n, minus, 2, right parenthesis time, and so on. cn+c(n−1)+c(n−2)+⋯+2c=c(n+(n−1)+(n−2)+⋯+2)

=c((n+1)(n/2)−1)

The last line is because 1 + 2 + 3 +...... n is the arithmetic series

Best-case running time:

Quicksort's best case occurs when the partitions are as evenly balanced as possible: their sizes either are equal or are within 1 of each other. The former case occurs if the subarray has an odd number of elements and the pivot is right in the middle after partitioning, and each partition has (n-1)/ 2 elements. The latter case occurs if the subarray has an even number n of elements and one partition has n/2 elements with the other having n/2-1.In either of these cases, each partition has at most n/2 elements.

Using big-Θ notation, we get the same result as for merge sort: Θ(nlog2n)

You might be interested in
lance measured 0.485 liter of water. Angel measured 0.5 liter of water. lance said, "My beaker has more water than yours because
nikdorinn [45]
No, if we were to make the decimal for angel it would be 0.500 which is more than lance, you can also round them
4 0
3 years ago
Read 2 more answers
Write a program that will open the file random.txt and calculate and display the following: A. The number of numbers in the file
Rama09 [41]

Answer:

Here is the C++ program:

#include <iostream>  //to use input output functions

#include <fstream>  //to manipulate files

using namespace std;  //to identify objects like cin cout

int main(){  //start of main function

  ifstream file;   //creates an object of ifstream

   file.open("random.txt"); //open method to open random.txt file using object file of ifstream

       

    int numCount = 0;  //to store the number of all numbers in the file          

    double sum = 0;   //to store the sum of all numbers in the file

    double average = 0.0;   //to store the average of all numbers in the file

    int number ; //stores numbers in a file

                 

        if(!file){   //if file could not be opened

           cout<<"Error opening file!\n";    }   //displays this error message

       

       while(file>>number){   //reads each number from the file till the end of the file and stores into number variable

           numCount++; //adds 1 to the count of numCount each time a number is read from the file          

           sum += number;  }  //adds all the numbers and stores the result in sum variable

           average = sum/numCount;  //divides the computed sum of all numbers by the number of numbers in the file

     

       cout<<"The number of numbers in the file: "<<numCount<<endl;  //displays the number of numbers

       cout<<"The sum of all the numbers in the file: "<<sum<<endl;  //displays the sum of all numbers

       cout<<"The average of all the numbers in the file: "<< average<<endl;  //displays the average of all numbers

       file.close();     }  //closes the file    

   

Explanation:

Since the random.txt is not given to check the working of the above program, random.txt is created and some numbers are added to it:

35

48

21

56

74

93

88

109

150

16

while(file>>number) statement reads each number and stores it into number variable.

At first iteration:

35 is read and stored to number

numCount++;  becomes

numCount = numCount + 1

numCount = 1      

sum += number; this becomes:

sum = sum + number

sum = 0 + 35

sum = 35

At second iteration:

48 is read and stored to number

numCount++;  becomes

numCount = 1+ 1

numCount = 2    

sum += number; this becomes:

sum = sum + number

sum = 35 + 48

sum = 83

So at each iteration a number is read from file, the numCount increments to 1 at each iteration and the number is added to the sum.

At last iteration:

16 is read and stored to number

numCount++;  becomes

numCount = 9 + 1

numCount = 10    

sum += number; this becomes:

sum = sum + number

sum = 674 + 16

sum = 690

Now the loop breaks and the program moves to the statement:

       average = sum/numCount;  this becomes:

       average = 690/10;

       average = 69

So the entire output of the program is:

The number of numbers in the file: 10                                                                                                           The sum of all the numbers in the file: 690                                                                                                     The average of all the numbers in the file: 69

The screenshot of the program and its output is attached.

5 0
3 years ago
1. What conversion factor should be used to convert from Gigaliters to liters?
Ilia_Sergeevich [38]
The conversion factor is 10 to the 9th power
5 0
3 years ago
Where should you look to find contact information about a company? I. on the company website II. at your local library III. in t
bixtya [17]

You should look on the company website in order to find contact information about a company,

The company website should contain the crucial Business Information, logical roadmap, contact information, easy navigation... The contact information should include number, email, address and a contact form. They should be easily accessible and visible.

4 0
3 years ago
Read 2 more answers
The ____ function displays the highest value in a range.
Monica [59]
Max()

------------------------------------------------------------
5 0
3 years ago
Read 2 more answers
Other questions:
  • It takes an older computer twice as long to send out a company's email as it does a newer computer. Working together, it takes t
    15·1 answer
  • Write a program that reads in text from standard input (hint: use Scanner) and prints out the number of words in the text. For t
    5·1 answer
  • / List the seven basic internal components found in a computer tower.
    5·2 answers
  • You may be guilty of plagiarism even if
    13·1 answer
  • Which is a good guideline to follow when choosing a background for your slides?. . A. Use a different background for each slide.
    8·1 answer
  • You can apply several different worksheet themes from which tab?
    10·2 answers
  • Web crawlers or spiders collect information from Web pages in an automated or semi-automated way. Only the text of Web pages is
    10·1 answer
  • When you expect a reader of your message to be uninterested, unwilling, displeased, or hostile, you should Group of answer choic
    15·1 answer
  • ¡Hola! He visto en muchos comentarios de Twitter "svd" cuando alguien dice "dale fav a este Tweet y siganse entre ustedes" y en
    8·1 answer
  • You can perform an in-place upgrade to Windows 7 from both Windows XP and Windows Vista
    11·2 answers
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!