Question

What is the Average time complexity of sequential search algorithm in a linked list?

Answer 1

Thanks for the question.

In any sequential (aka linear) search, we are iterating over each value in the container(in this case its linked list). There can be two possible scenarios - the element we are searching may exist at any index position in the container( or linked list) or the element may not exist.

To compute average case complexity, we consider all possible inputs and compute for all of the inputs. We sum all the calculated values and divide the sum by total number of inputs. We must know (or assume) uniform distribution of all possible cases. Let us assume that all cases are uniformly distributed (including the scenario where the element we are searching is not present in the linked list). So we sum all the cases and divide the sum by (n+1). Following is the value of average case time complexity.

Average Case Time =

                  =

                  = Θ(n)

Hence, the average time complexity for sequential search is linear or of order n where n is the number of elements we have in the linked list.