What is the time complexity of the following code? Please show all steps to prov

Question

What is the time complexity of the following code? Please show all steps to prove it and explain why.

"This function divides an array a[l],…, a[r] into a[l],…, a[m] and a[m+1],…, a[r], finds the maximum elements in the two parts (recursively), and returns the larger of the two as the maximum element in the whole array. It assumes that Item is a first-class type for which > is defined. If the array size is even, the two parts are equal in size; if the array size is odd, the sizes of the two parts differ by 1. Item max(Item a[], int l, int r)

{
if (l == r) return a[l];
int m = (l+r)[/]2;
Item u = max(a, l, m);
Item v = max(a, m+1, r);
if (u > v) return u; else return v;
}"

Source: Sedgewick, Robert. Algorithms in C++, Parts 1-4: Fundamentals, Data Structure, Sorting, Searching (pp. 210-211). Pearson Education. Kindle Edition.

Explanation / Answer

it is similar as binary search.

1) if l==r ..............1 time

2) l+r/2.................1 time

3) calculating max in first half portion ...........logn time

4) calculating max in second part ...............logn

5) comparing u and v, prints greater one.......1 time

so total time complexity= O(1)+O(1)+O(logn)+O(logn)+O(1)=2logn=logn

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

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