Write a recurrence relation for the run time

Assignment Help Data Structure & Algorithms

Reference no: EM131875666

Question 1.

a) Write a recursive Java function, void max( int[] A, int lo, int hi ), that finds the maximum value among the array elements A[lo], A[lo+1], . . . , A[hi], using the tournament method. (That is, find the maximums in two halves of the array and then compare them.)

b) This function can be used to find the max of an N-element array by calling max(A, 0, N-1). Write a recurrence relation for the run time, T(N ), of the function.

c) Use the Master Theorem to find T (N ). (Explain your reasoning. You shouldn't be surprised by the answer!)

Question 2.

Suppose that a recursive algorithm divides a problem of size n into 4 problems of size n/2. The amount of extra work that is done to split the problem into parts and to combine the results from processing the parts is Θ(n2). Write a recurrence relation for the run time of the algorithm and use the Master Theorem to find the run time. How does the answer change if the extra work has run time Θ(n³/2)?

Reference no: EM131875666

Questions Cloud

Pharmacological and physiological effects of substance use : Select two substances from the following and describe at least two pharmacological and physiological effect of each (200-350 words each).

How you solved the social security crisis : Based upon your research and the results of the Social Security Game, write a report that addresses how YOU solved the Social Security crisis.

Develop outline for sex-education class for a group of teens : Develop an outline for a sex-education class for a group of teens. What type of education would be most effective and why?

What is the purpose of the capital projects fund : What is the purpose of the capital projects fund? What is the purpose of the debt service fund? What is inter-period equity

Write a recurrence relation for the run time : CPSC 327 - Write a recurrence relation for the run time, T(N ), of the function and How does the answer change if the extra work has run time T(n3/2)

Describe way to how intervention is tackling teenage suicide : Describe ways as to how this intervention is tackling teenage suicide. Is the method effective? Is it prominent as a help hotline for teenagers to use in the co

What is the minimum acceptable price of this special order : Polar Manufacturing has excess capacity. For Polar Manufacturing, what is the minimum acceptable price of this special order

Purposes of computing its cash flow return on investment : What is MBA Inc.'s gross investment (GI) for purposes of computing its cash flow return on investment (CFROI)?

Analyze hps use of bribery to obtain foreign contracts : Analyze HP's use of bribery to obtain foreign contracts based on a utilitarian/consequentialist approach.

User Account

All Pages