Linear search Algorithm & its complexity.

Question

hello; how we can find Linear search Algorithm & its complexity. regards sumaira manzoor

Vulpes · Answer

'Big O' notation is a form of asymptotic notation. Check this article: http://en.wikipedia.org/wiki/Big_O_notation If you have a list of n items and you're doing a search for one of them which you know only occurs once then the probability that it will be the first item is 1/n that it will be the second item is also 1/n and so on for each item. So the average number of items to be examined before you find the item you're looking for is given by: (1 + 2 + 3 + .... + n)/n which is n * (n + 1)/2/n which is (n + 1)/2. The order of complexity is therefore O(n) as given in the table in the above article.

sumaira manzoor hussain khan · Answer

hello sir; but the question is how we can find complexity of linear search using asumptotic notation.

Vulpes · Answer

A linear search is the simplest possible search algorithm where you simply iterate through a list of items until you find the item you're looking for. Clearly the time it takes to find an item will be proportional to the number of items in the list (n say). If an item occurs just once in the list then on average (n + 1)/2 items will need to be examined before a match is found. Foe example if a list of ints contains the 5 numbers 1234 and 5 and you're looking for a random number in this range then on average you'll need to examine (5 +1)/2 = 3 numbers until you find the one you're looking for. In 'big O' notation a linear search algorithm is O(n).