COMPUTER SCIENCE AND ENGINEERING
DATA STRUCTURES
|
Question
[CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
|
|
|
log 2 n
|
|
|
n/2
|
|
|
log 2 n-1
|
|
|
n
|
Detailed explanation-1: -5. In the worst case, the number of comparisons needed to search a singly linked list of length n for a given element is? Explanation: In the worst case, the element to be searched has to be compared with all elements of the linked list. 6.
Detailed explanation-2: -So, in the worst case for a list of length n, we will have to go to each node for comparison and thus, we would be needing ‘n’ comparisons.
Detailed explanation-3: -What is the number of comparisons required to search an element in a sorted linked list in the worst case? As per the answer key the correct answer is n. But i thought this way, in a sorted linked list, the search needn’t move through all the elements.
Detailed explanation-4: -The Best Case occurs when the target element is the first element of the array. The number of comparisons, in this case, is 1. So, the time complexity is O(1) .
Detailed explanation-5: -Time Complexity for searching in a sorted linked list = O(n). Since linked list is sorted so in worst case insertion will take O(N).