Let A[1::n] be an array of numbers. To find the largest number in A, one way is

Question

Let A[1::n] be an array of numbers. To find the largest number in A, one way is to divide A into two halves, recursively nd the largest number in each half, and pick the maximum between the two.

(a) Write a recursive algorithm to implement the above scheme. Write a recurrence relation describing the running time of the algorithm and solve it to give a tight bound on the running time of this al- gorithm.

(b) Does this recursive algorithm perform better than an incremental algorithm that computes the largest element in A by iterating through the elements of A? Explain.

Explanation / Answer

Program for Max and Min:

2. Finding complexity:

When n is a power of two, n = 2k

-WHERE k is positive integer

T(n) = 2T(n/2) + 2

           = 2(2T(n/4) + 2) + 2

           = 4T(n/4) + 4 + 2

           .

           .

           .

           = 2k-1 T(2) + (1ik-1) 2k

           = 2k-1 + 2k – 2

           = 3n/2 – 2 = O(n)

Note that 3n/2 – 2 is the best, average, worst case number of comparison when n is a power of two.

2n – 2 comparisons for the Straight Forward technique, this is a saving of 25% in comparisons. It can be demonstrated that no calculation is under 3n/2 – 2 comparisons.

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.