Bounded-error unstructured search query complexity is Theta of square root N

The lower bound for both tasks is [F1], so each complexity is at least a positive constant times $\sqrt{N}$.

For $N\ge 3$, the one-run success probability in [F2] is at least $1-1\mathrm{/}N\ge 2\mathrm{/}3$. For $N=1$, [F2] gives certainty. For $N=2$, run the fixed-one procedure twice with fresh registers and independent measurements, returning a verified candidate if either run verifies one. Each run has success probability at least $1\mathrm{/}2$ by [F2]; conditional independence of the fresh runs gives failure probability at most $(1-1\mathrm{/}2{)}^2=1\mathrm{/}4$, hence success at least $3\mathrm{/}4$.

Verification prevents a false yes on $0^N$, by [F2] and [F4]. On each singleton input the procedures in step 1.2 return its marked coordinate with probability at least $2\mathrm{/}3$. They are therefore bounded-error solvers for both the decision and finding tasks. The two-run case uses at most twice the cost in [F3], and the other cases use at most one run, so [F5] bounds their worst-case query cost by $6\sqrt{2N}=O(\sqrt{N})$.

Combining steps 1.1 and 2.1 gives matching positive constant lower and upper multiples of $\sqrt{N}$ for both decision and finding. All statements concern standard bit queries; nonoracle gate and preprocessing costs remain separate.