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
Burka [1]
3 years ago
6

Suppose that the splits at every level of quicksort are in the proportion 1 − α to α where 0 < α ≤ 1/2 is a constant. Show th

at the minimum depth of a leaf in the recursion tree is approximately
Computers and Technology
1 answer:
Lady_Fox [76]3 years ago
4 0

Answer:

Explanation:

The minimum depth occurs for the path that always takes the smaller portion of the

split, i.e., the nodes that takes α proportion of work from the parent node. The first

node in the path(after the root) gets α proportion of the work(the size of data

processed by this node is αn), the second one get (2)

so on. The recursion bottoms

out when the size of data becomes 1. Assume the recursion ends at level h, we have

(ℎ) = 1

h = log 1/ = lg(1/)/ lg = − lg / lg

Maximum depth m is similar with minimum depth

(1 − )() = 1

m = log1− 1/ = lg(1/)/ lg(1 − ) = − lg / lg(1 − )

You might be interested in
What do you mean by data sequencing​
Shalnov [3]

Answer:

Data sequencing is the sorting of data for inclusion in a report or for display on a computer screen.

Explanation:

8 0
2 years ago
Each row in a database is a set of unique information called a(n)
blondinia [14]

A row, which is also called a tuple.

4 0
3 years ago
Read 2 more answers
Read the following scenario: A project will require more people than originally estimated. Identify the possible risks to the pr
egoroff_w [7]
A ideas and creativity
8 0
3 years ago
Read 2 more answers
Write a program that produces this output:
AveGali [126]

Answer:

void printC()  

{  

   int i, j;  

   for (i = 0; i < 4; i++) //i indicate row number. Here we have 5 rows

       {  

         printf("C"); //print C for every row  

         for (j = 0; j < 6; j++) //j indicate column number. Here we have 7 Rows

         {  

           if (i == 0 || i == 4) //For first and last row  

               printf("C"); //print 'CCCCCCC'

          else if (i = 1|| i= 3) //for Second forth row  

                printf("C        +      +"); //print 'C    +    +'

          else if (i = 2) For second row  

                printf("C       +++++"); //print 'C +++++'

           else

               continue; //to jump to next iteration

         }  

         printf("\n"); // print in next line

}  

}

4 0
3 years ago
What helps companies and organizations to target masses of people, provide 24/7 services, and deliver better marketing in a chea
Sever21 [200]
The money their making
6 0
3 years ago
Other questions:
  • 3k means about 3 thousand bytes. how would you express two hundred million bytes?
    8·1 answer
  • Which of the following typically have the highest auto insurance premiums?
    14·1 answer
  • To change a chart's data series, make the chart active, then in the data group on the chart tools design tab, click the _____ bu
    9·1 answer
  • What type of program would you use to create a personal budget?
    9·1 answer
  • What feature of a word processing program helps you to easily check and correct spelling mistakes?
    9·1 answer
  • PLEASE HELP ASAP!!!
    8·1 answer
  • Which of the following are not parts of a message? Select all that apply.
    12·1 answer
  • What is the difference between C and C++. If I know C, will it be hard to lean C++?
    15·1 answer
  • Provides images of weather systems, and helps to track storms at different altitudes
    7·1 answer
  • Give 4 examples of mnemonic codes, and what do they do?
    15·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!