(23) A linear search method on n list elements has these characteristics t has O
ID: 3147765 • Letter: #
Question
(23) A linear search method on n list elements has these characteristics t has O( n ) as a worse case scenario since you may be required to check and verify every element in the list or array there are n ÷ 2 average number of comparisons for a typical list What is the average number of comparisons for the list given below? 20, 70, 80, 50,40, 10,100, 120,60, 30,90, 110 } (a) 3 Here is the Binary Search routine: Step 1 Step 2 (b) 4 (d) 0 (24) obtain the middle element in the list if the middle element equals to the searched value, then the process ceases otherwise, there are two possible cases Step 3 The value to search is less than the middle element. In this case, proceed to Step 1 for the portion of the list that exists before middle element. The value to search value is greater than the middle element. In this case, proceed to Step 1 for the portion of the list that exists after middle element. For the sorted list given below, how many iterations are required to locate the element 95? 10,20,40, 50,70, 85,90, 95,100 (a) 2 A binary search complexity is o(LOG 2 (n)) which means that in a list of n = 50 elements, the process may take a maximum of (a) 8 (b) 5 (d) 10(e) 1 (25) terations. (b) 4 (c) 10 (d) 6 (e) 2Explanation / Answer
(23) As given, there are n/2 average number of comparisons for typical list, where 'n' is the number of elements in the list. In given list, n=12,
Therefore, average number of comparisons for given list = 12/2 = 6. (option e)
(24) Given list is {10, 20, 40, 30, 70, 85, 95, 100}
In 1st iteration, n=9, middle element = [n/2] = [9/2] = [4.5] = 4
4th element in the list is 70 (as indexing starts from i=0). As 70<95, therefore now the list of concern is {85, 90, 95, 100}
Now,
2nd iteration, n=4, middle element = [4/2] = 2
Now, 2nd element in {85, 90, 95, 100} is 95 (as indexing starts from i=0).
Therefore element 95 is found.
Therefore, number of iterations taken = 2. (option a)
(25) As given, maximum iterations = log2(n). Since log2(50) = 5.64,
For n=50, process may take maximum of 6 iterations. (option d)
Please do rate me and mention doubts, if any, in the comments section.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.