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
4. Contoso, Ltd. has a vigorous Office 365 and Azure cloud-service presence.
OverLord2011 [107]

Answer:

Contoso has an on-premises identity infrastructure. The infrastructure includes servers that run Active Directory Domain Services

Explanation:

3 0
3 years ago
You entered the following line of code in IDLE.
AlexFokin [52]

Guess is a string. By default the input function returns string types.

8 0
3 years ago
Read 2 more answers
An office uses an application to assign work to its staff members. The application uses a binary sequence to represent each of 1
fenix001 [56]

Answer: I believe the answer is: A, 5.

Explanation:

6 0
3 years ago
Write a telephone lookup program. Read a data set of 1,000 names and telephone numbers from a file that contains the numbers in
morpeh [17]

Answer:

See explaination

Explanation:

PhoneLookup.java

import java.io.FileReader;

import java.io.IOException;

import java.util.Scanner;

public class PhoneLookup

{

public static void main(String[] args) throws IOException

{

Scanner in = new Scanner(System.in);

System.out.println("Enter the name of the phonebook file: ");

String fileName = in.nextLine();

LookupTable table = new LookupTable();

FileReader reader = new FileReader(fileName);

table.read(new Scanner(reader));

boolean more = true;

while (more)

{

System.out.println("Lookup N)ame, P)hone number, Q)uit?");

String cmd = in.nextLine();

if (cmd.equalsIgnoreCase("Q"))

more = false;

else if (cmd.equalsIgnoreCase("N"))

{

System.out.println("Enter name:");

String n = in.nextLine();

System.out.println("Phone number: " + table.lookup(n));

}

else if (cmd.equalsIgnoreCase("P"))

{

System.out.println("Enter phone number:");

String n = in.nextLine();

System.out.println("Name: " + table.reverseLookup(n));

}

}

}

}

LookupTable.java

import java.util.ArrayList;

import java.util.Collections;

import java.util.Scanner;

/**

A table for lookups and reverse lookups

*/

public class LookupTable

{

private ArrayList<Item> people;

/**

Constructs a LookupTable object.

*/

public LookupTable()

{

people = new ArrayList<Item>();

}

/**

Reads key/value pairs.

atparam in the scanner for reading the input

*/

public void read(Scanner in)

{

while(in.hasNext()){

String name = in.nextLine();

String number = in.nextLine();

people.add(new Item(name, number));

}

}

/**

Looks up an item in the table.

atparam k the key to find

atreturn the value with the given key, or null if no

such item was found.

*/

public String lookup(String k)

{

String output = null;

for(Item item: people){

if(k.equals(item.getName())){

output = item.getNumber();

}

}

return output;

}

/**

Looks up an item in the table.

atparam v the value to find

atreturn the key with the given value, or null if no

such item was found.

*/

public String reverseLookup(String v)

{

String output = null;

for(Item item: people){

if(v.equals(item.getNumber())){

output = item.getName();

}

}

return output;

}

}

Item.java

public class Item {

private String name, number;

public Item(String aName, String aNumber){

name = aName;

number = aNumber;

}

public String getName(){

return name;

}

public String getNumber(){

return number;

}

}

input.txt

Abbott, Amy

408-924-1669

Abeyta, Ric

408-924-2185

Abrams, Arthur

408-924-6120

Abriam-Yago, Kathy

408-924-3159

Accardo, Dan

408-924-2236

Acevedo, Elvira

408-924-5200

Acevedo, Gloria

408-924-6556

Achtenhagen, Stephen

408-924-3522

Note: Replace all the "at" with at symbol

4 0
3 years ago
Whatis NOT a key factor while designing a website?
Vaselesa [24]

Answer: Complexity

Explanation: Web designing is referred as the designing of a web page for different purposes such as online business,etc. The most important factor is usability for the improvement in performance of any site and keeping it successful.

It should be user friendly so that interaction and understanding between user and web page can easy.Consistency is also a feature which ensure that web page opened in any browser should have similar quick working.

But there should be no complexity present in the web design which can cause misunderstand with the user and functioning.

7 0
3 years ago
Other questions:
  • Privileged instructions 1) generate an interrupt so they can execute before non-privileged instructions. 2) are valid only when
    5·1 answer
  • What tool enables you to easily delete, add, or resize filesystems without regard to their physical locations on a hard disk?
    13·1 answer
  • Which line in the following program contains the header for the showDub function? 1 #include«iostream» 2 using namespace std; 4
    15·1 answer
  • True or False
    10·2 answers
  • Which value can be entered to cause the following code segment to display the message: "That number is acceptable." int number;
    11·1 answer
  • To open a Google Doc in another software application, the user must first download it. True or false?
    12·2 answers
  • CAN SOMEONE PLEASE DO THESE FOR ME I WILL GIVE BRAINLIESR AND 20 POINTS PLEASE ITS ONLY 5 QUESTIONS PLEASEEEE
    12·1 answer
  • Julie is purchasing new shoes on a website for her favorite store. Which of the following would indicate that a website is a sec
    6·1 answer
  • Design the following webpage using suitable html code .
    11·2 answers
  • Animals living in burrows under the ground is an interaction between the biosphere and the
    11·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!