In the book "Introduction to quantum algorithms via linear algebra" they said that:
"The problem that Grover’s algorithm solves is finding a “needle in a haystack.” Suppose that we have a large space of size N, and one of the elements is special. It may be a solution to some problem that we wish to solve—one we could verify if we knew it. Then a classical algorithm in worst case would have to examine all the elements, and even a randomized algorithm expects to look at N/2 elements."
I dont understand why a randomized algorithm expects to look at N/2 elements? Can someone explain it? Thank you.
The probability of getting it on your $k$th draw is $$ \frac{N-1}{N} \cdot \frac{N-2}{N-1} \cdots \frac{N - k + 1}{N - k + 2} \cdot \frac{1}{N - k + 1} = \frac{1}{N} $$ We thus calculate the expected value for when we draw the needle as $$ \sum_{k = 1}^N k \cdot \frac{1}{N} = \frac{1}{N} \sum_{k =1}^N k = \frac{1}{N} \frac{N(N + 1)}{2} = \frac{N+1}{2} $$ which is big O the same as your source's claim.