Question 3. [12 marks in total a. (4 marks) Provide sample inputs for both best

Question

Question 3. [12 marks in total a. (4 marks) Provide sample inputs for both best and worst case time com- plexities for the following search method public static int mySearch (int [] arr, int target) int result -1 for(int i-arr.length-1; i>-0; i--) t if (arr [i]target) 1 resulti return result; You answer must be of the form: Best case time complexity: O) when arr-, target - . Worst case time complexity: O when arr -[), target - b. (4 marks) Re-write the method from task a. so that its best case time complexity improves (it takes less time in the best case scenario) c. (4 marks) (Advanced) Determine the minimum number of searches (k) that must be performed on an array to justify sorting it once (using merge sort) before performing k binary searches rather than performing k linear searches over an unsorted arrav. Worst case time complexities of relevant algorithms . Linear Search: O(n) ·Binary Search: O(log-n) . Merge Sort: O(nlogzn)

Explanation / Answer

Solution:-

Part a.)

In the code written above, the for loop always executes till the length of the array in any case. So in all cases(Best and Worst), the time complexity is :- O(n)

So the answer:-

Best case time complexity:- O(n) when arr = {1, 2, 3, 4}, target = 1.

Worst case time complexity:- O(n) when arr = {1, 2, 3, 4}, target = 4.

Part b.) Improving best case time complexity, return as soon as the target is matched.

public static int mySearch(int[] arr, int target) {

int result = -1;

for(int i = arr.length-1; i>=0; i--) {

if(arr[i] == target) {

return i; //return the index when found  

}

}

return result;

}

In the above code, the complexity in Best case is:- O(1).

Part c.) Suppose the Size of the array is 16.

So, Worst time complexity in linear search:- n = 16 Searches required.

In Sorting the array, the number of operations performed, is(n*log2n) = (16*4) = 64

And in each binary search, the number of searches required in worst case is:- logn = 4.

16*n > 64 + 4n, for sorting to be justified(n = number of searches)

so, 12n > 64 i.e. n > 5, so n = 6, 7, 8, 9 ....

So, if the number of searches is greater than 5, we should rather sort the array and perform binary search.

======================SOLUTION ENDS=================

Note:- Please upvote if it helped, else do comment on the part you didn't understand, i'll be happy to help.

Thanks!

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

---

---

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