알고리즘
[Introduction to Algorithms, CLRS] Exercises 2.2-3
nevermet
2017. 12. 23. 17:51
This is a solution for Introduction to Algorithms. I write this for my study purpose.
Exercises 2.2-3
Consider linear search again (see Exercise 2.1-3). How many elements of the input sequence need to be checked on the average, assuming that the element being searched for is equally likely to be any element in the array? How about in the worst case? What are the average-case and worst-case running times of linear search in Θ-notation? Justify your answers.
Answer:
- On the average n/2 elements need to be checked.
- In the worst case, n elements need to be checked.
- In Θ-notation, Θ(n) in both cases.