Question

What is the order of the operation that determines if an item is there (using Big-O notation):

a). in a sorted, array-based implementation, using the best algorithm?

b). in an unsorted list, array-based implementation?

c). How about a sorted, linked implementation?

d). Or an unsorted, linked implementation?

Answer 1

a)  O(log n)
because we can use binary search. and it only takes O(log n) using binary search.

b)  O(n)
we have to use linear search here since the array is not sorted. so, it takes O(n)

c)  O(n)
even if the linked list is sorted, we don't have the mechanism to do binary search on it.
we will have to go through all nodes of list sequentially.
so, In worst case we might have to go through all nodes.
so, it also takes O(n)

d)  O(n)
we will have to go through all nodes of list sequentially.
so, In worst case we might have to go through all nodes.
so, it also takes O(n)