6. Given the following Java code for a binary search algorithm, answer each ques

Question

6. Given the following Java code for a binary search algorithm, answer each question: boolean binarySearch( int [] values, int target, int low, int high )f int midpoint = (first + ïast) >> 1; if( low > high ) return false; if( target values [midpoint] ) return true; else if( target > values [midpoint] ) return binarySearch(values, target, midpoint + 1, high); return binarySearch(values, target, low, midpoint - 1); (a) (2 points) What is the best case complexity when searching for a single target item in values? Answer (2 points): (b) (2 points) What is the worst case complexity when searching for a single target item irn values! Answer (2 points) (c) (3 points) What is the worst case complexity when searching for n2 target items in values? Answer (2 points):

Explanation / Answer

A) Best Case happens when target is in the middle So it will take O(1) time

B) Worst Case happens when target is not found in the values array, So it will take O(log n) time

C) One Search takes O(log n) time in worst case, when we search for n2 element then it will take
n2 x logn time in worst case i.e O(n2 log n)


Thanks, PLEASE UPVOTE

Related Questions

Navigate

• Browse (All)
• Browse 6
• Subjects

---

---

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