Collision problem

The r-to-1 collision problem is an important theoretical problem in complexity theory, quantum computing, and computational mathematics. The collision problem most often refers to the 2-to-1 version:^[1] given ${\displaystyle n}$ even and a function ${\displaystyle f:\,\{1,\ldots ,n\}\rightarrow \{1,\ldots ,n\}}$, we are promised that f is either 1-to-1 or 2-to-1. We are only allowed to make queries about the value of ${\displaystyle f(i)}$ for any ${\displaystyle i\in \{1,\ldots ,n\}}$. The problem then asks how many such queries we need to make to determine with certainty whether f is 1-to-1 or 2-to-1.