Solution Found!
Analyze the average-case performance of the linear search
Chapter 3, Problem 23E(choose chapter or problem)
QUESTION:
Problem 23E
Analyze the average-case performance of the linear search algorithm, if exactly half the time the element x is not in the list and if x is in the fist it is equally likely to be in any position.
Questions & Answers
QUESTION:
Problem 23E
Analyze the average-case performance of the linear search algorithm, if exactly half the time the element x is not in the list and if x is in the fist it is equally likely to be in any position.
ANSWER:
Solution
In this question we have to analyze the average case performance of the linear search algorithm.
Step 1
Case 1
If exactly half the time the element x is not in the list
Since the element is not in the list it’s complexity is