What is the time complexity of Linear search assuming a sort

What is the time complexity of... Linear search assuming a sorted array? Linear search assuming a sorted linked list? Binary search assuming a sorted array? Binary search assuming a sorted linked list? Selection sort on random data? Quicksort on random data?

Solution

a) O(n)

Linear search assuming sorted array:

In linear search, in worst case we have traverse the array from start to end, so

Time complexity = O(n)

b) O(n)

Linear search assuming sorted linked list:

Again, linear search assuming sorted linked list, in worst case we have traverse the array from start to end, so

Time complexity = O(n)

c) O(logn)

Binary search assuming sorted array:

In case of Binary search assuming sorted array, time complexity is O(logn). Binary search divides the array in two equal parts untill we find the element where only one subpart contains the element. So we don\'t need to search in second subpart of the array. so time complexity is O(logn).

d) O(n)

In case of Binary search using sorted linked list, we can not directly access list element at an index i directly, so binary search can not be performed.

e) Worst case time complexity of selection sort is O(n^2).

f) Worst case time complexity of quick sort is O(n^2), But average time complexity is O(nlogn).