Question

What is the average number of nodes accessed in search for a particular element in an unordered list? In an ordered list? In an unordered array? In an ordered array?

Answer 1

Answer and Explanation:

1. In the case of the unordered list, the search algorithm is applied as the binary search would not be worked here also the time complexity for searching for n number of elements is O(n)

So the average number of nodes for the unordered list is n ÷ 2

2. For the ordered list, the same is to be considered i.e. n ÷ 2

Also it deals with the recepts of items and every item contains a relative position that represents an attribute of an item

3. For the unordered array, the same is to be considered i.e. n ÷ 2 but in this no sequence is followed

4. For the ordered array, the average number of nodes is
`(log_2n) - 1` and in this, the binary search is to be considered