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
Answer the following questions:
victus00 [196]

Answer:

The answer to the following questions can be given as:

Question: 1

value of foo is = 1020

Question: 2

Output of the code is = false

Question: 3

function add(a, b)

{

 return a && b ? a + b : function (c) { return a + c; };

}

var a=add(2,5);

var x=add(2)(5);

print(a);

print(x);

output:  

7

7

Question: 4

"goh angasal a m'i"

Question: 5

In this we check that if in the window a foo function exists. otherwise we set windows.foo to bar.

Question: 6

first alert shows the value "Hello World";

second alert shows value ReferenceError, In this bar not defined.

Question: 7

The value of foo.length is  2

Question: 8

The value of foo.x is undefined

Question: 9

Function print = "one", "three", "two" .

Question :10

It is difficult to define because doSomethingElse() function is not defined.

Explanation:

In question 1 the value of the foo variable is 1020 because we perform the string concat operation.

In question 2 Output of the code is false because float value keeps in binary and when we convert 0.1 or 0.2 to binary so it is not the same.

In question 3 the output of both functions is 7.

In question 4 the output is goh angasal a m'i because In this code we use the reverse() function, split() function and join() function. Reverse function reverses the value. split function splits the value and join function join all the value of the string in a line.

In question 5 we check the value.

In question 6, the first output is Hello World and second is ReferenceError.

In question 7, the value of foo.length is 2 because this foo array we insert only 2 values.

In question 8, the value of foo.x is undefined because in the variable we reset the value of foo all together, so foo.x value is undefined.

In the question 9 function print "one",  

"three",  

"two" because In the function first, we print the message that is "one" then we define a function in this function we print the value  

"two" but before creating object we call the "three" so the print value is "one",  

"three",  

"two".

In question 10 function, the output of this function is undefined.

3 0
3 years ago
Gettier contributed to what we know about the __________ model, while Rosch contributed to what we know about the __________ mod
svet-max [94.6K]

Gettier contributed to what we know about the exemplar model, while Rosch contributed to what we know about the prototype model. Prototype and exemplar theories are both versions of statistical theories of concepts. Prototype theories hold that concepts represent categories by means of a summary of the typical properties that category members possess, while exemplar theories hold that concepts represent categories by means of a cluster of individual category members that may be used to extract the statistical central tendency of the category.

6 0
3 years ago
Read 2 more answers
A customer has a new laptop with wireless WAN capabilities; however, the software does not connect to the Internet. What would y
LUCKY_DIMON [66]

Answer:

Check below for the explanation

Explanation:

The following suggestions will be given to the customers:

  • Go to network settings and check the WIFI settings to confirm whether the WIFI connection is on. Switch the WIFI to the on position if it is off.
  • The customer should check if the wireless driver is installed on the computer, if the driver is not installed, he should try to install it
  • The customer should check all the available access points and confirm if their signal strengths are strong enough to allow for any connections. Restart the access point to enhance proper connection.
  • Check to see if your operating system is updated to support your internet connection. You can update your operating system to the latest version
  • Run a Network Diagnostics on your computer. This will run a couple of tests to see what’s possibly causing your Wi-Fi issues.
5 0
3 years ago
Output a table that show the cube of the numbers 1-15<br> (C++)
Rainbow [258]

Answer:

The c++ program to display cube of numbers from 1 to 15 is given below.

#include <iostream>

using namespace std;

int main() {    

   // variables declared and initialized  

   int num = 15, k, cube;    

   cout << " Cubes of numbers from 1 to 15 are shown below " << endl;    

   for( k = 1; k <= num; k++ )

   {

       // cube is calculated for each value of k and displayed

       cube = k * k * k ;

       cout << " \t " << cube << endl;

   }

return 0;

}

 

OUTPUT

Cubes of numbers from 1 to 15 are shown below  

  1

  8

  27

  64

  125

  216

  343

  512

  729

  1000

  1331

  1728

  2197

  2744

  3375

Explanation:

The variables are declared and initialized for loop, cube and for condition in the loop – k, cube, num respectively.

Inside for loop which executes over k, beginning from 1 to 15, cube of each value of k is calculated and displayed. The loop executes 15 times. Hence, cube for numbers from 1 to 15 is displayed after it is calculated.

   for( k = 1; k <= num; k++ )

   {

      cube = k * k * k ;

       cout << " \t " << cube << endl;

   }

In the first execution of the loop, k is initialized to 1 and variable cube contains cube of 1. Hence, 1 is displayed on the screen.

In the second execution, k is incremented by 1 and holds the value 2. The variable cube contains cube of 2, which is calculated, and 8 gets displayed on the screen.

After each execution of the loop, value of k is incremented.

After 15 executions, value of k is incremented by 1 and k holds the value 16. This new value is greater than num. Hence, the loop terminates.

3 0
3 years ago
Write a JAVA program containing a method called hasEight(), which takes an int as input and returns true if the number contains
skelet666 [1.2K]

Here's my code for that, consider it under the WTFPL (http://www.wtfpl.net/). Here is a pastebin of the code, as to avoid text formatting. (Link: https://pastebin.com/S3BDGxqm Raw: https://pastebin.com/raw/S3BDGxqm)

package javaapplication6;

import java.util.Scanner;

public class JavaApplication6 {

   

   public static void main(String[] args) {

       

       Scanner myScanner = new Scanner(System.in);

       

       boolean a;

       int s;

       System.out.println("Enter an int");

       s = myScanner.nextInt();

       a = hasEight(s);

       System.out.println(a);

       

   }

   private static boolean hasEight(int s)

   {

       String str = String.valueOf(s);

       return str.contains("8");

   }

   

}

7 0
3 years ago
Other questions:
  • suppose you need to verify how to correctly use commas. you pen your English textbook and scan the chapter titles in which one w
    15·1 answer
  • How to burn mp3 on dvd
    13·2 answers
  • You should use the longest possible shutter speed for all firework photographs.
    8·2 answers
  • How has the use of computers impacted business
    13·2 answers
  • "assignment is to create a program that will read a value from an array, and then place this value in another array with the loc
    10·1 answer
  • Which of the following statements is correct?
    11·1 answer
  • Which of the following statements is NOT true about url extension?
    10·2 answers
  • When importing data using the Get External Data tools on the Data tab, what wizard is automatically
    11·1 answer
  • Identify the correct answer in each item. Write your answer on the blank provided before
    13·1 answer
  • I need a solution for this problem asap.
    7·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!