Time Complexity Analysis - Grover

This is going to be a geometric proof to show that the number of Grover iterations we must do to achieve a high probability of measuring the winner state is bounded by $O(\sqrt{N})$.

Equal superposition

We will carry forward what we’ve learned from the past lessons and start with the situation where some arbitrary state $|x\rangle$ could be measured from the superposition, and it lies in between $|w\rangle$ and $|E\rangle$ in the state space. The $|x'\rangle$ state is orthogonal to $|w\rangle$ and the angle between $|x'\rangle$ and $|E\rangle$ is $\Delta$