Solve the recurrence using the recursion trees method

Assignment Help Basic Computer Science

Reference no: EM13692190

Consider the following recurrence: T(n) = 2T(n/2)+nlgn

Let's use a base-case of T (2) = 2 and let's assume n is a power of 2.

Part (a) "Guess and prove by induction" method, considering the following steps.

Step i. Try to prove by induction that T(n) <= cnlgn. (assume inductively that T(n') <= cn'lgn'for all n' < n and try to show it holds for n. This guess is incorrect and so your proof should fail.) Point out where this proof fails.

Step ii. Use the way the above proof failed to suggest a better guess g(n). Explain this guess and prove by induction that T (n)<= g(n) as desired.

Step iii. give a proof by induction to show that T(n) >= c'g(n) where c' > 0 is some constant andg(n) is your guess from (b). Combining this with (b), this implies that T (n) = bigtheta(g(n)).

Part (b) Solve the recurrence using the recursion trees method.

You have to satisfy the requirements specified in the instruction.

Reference no: EM13692190

Questions Cloud

What is the final temperature in a squeezed cold pack : Question- What is the final temperature in a squeezed cold pack that contains 48.5g of NH4NO3 dissolved in 125 mL of water. Assume a specific heat of 4.18J/(g??C) for the solution, an initial temperature of 28.0C

Write a recursive descent parser : Perform the pairwise disjointness test for each rule to show that this grammar allows top-down parsing.

Define what is the final volume of the gas : Question- A sample of gas occupies a volume of 70.0 mL. As it expands, it does 145.6 J of work on its surroundings at a constant pressure of 783 torr. What is the final volume of the gas

What is the entropy change for a particle in this system : Question- A gaseous system undergoes a change in temperature and volume. What is the entropy change for a particle in this system if the final number of microstates is 0.448 times that of the initial number of microstates

Solve the recurrence using the recursion trees method : Guess and prove by induction method - Solve the recurrence using the recursion trees method.

Aqueous sodium bicarbonate be sufficiently basic : Question- The pKa of benzoic acid is 4.2, whereas that of carbonic acid, H2CO3, is 6.4. On the basis of this information, would aqueous sodium bicarbonate be sufficiently basic to deprotonate benzoic acid? Explain your reasoning.

What would its activity be 2 cm from the detector : Question- When a sample of phosphorus-32 (a beta-emitter used to treat leukemia and pancreatic cancer) was placed 1 cm from the detector, the intensity of its radiation was measured to be 491 counts per second. What would its activity be 2 cm from..

Describe process management and memory management : Describe the process management and memory management activities performed by the Operating System?

Derive a contradiction : State your assumptions for a proof by contradiction - Derive a contradiction.

User Account

All Pages