Post Closed as "duplicate" by David Richerby, Evil, Yuval Filmus, Juho, Thomas Klimpel of
3 edited tags
| link
2 edited tags
| link
1
source | link

How to prove that average complexity is N/2 for linear search in the unsorted array

All tutorials on algorithms show the complexity for the linear search in the unsorted array in the average case as N/2. I understand that the average case means the items in the list are randomly distributed.

Can anyone show how I would arrive at N/2 if I have items randomly distributed? Or does it come out of randomly shuffling array bazillion times and recording the number of operations?