About factoring a composite integer $N$. As far as I know very little is known about how efficient an algorithm can be, but how about the opposite? What can be proved about how efficient it can't be?
Trial and error has a time complexity of $\sqrt N$ since it's enough to test for factors up to $\sqrt N$. Pollard Rho is supposed to have time complexity $\sqrt p \approx N^{1/4}$ where $p\leq \sqrt N$ is the largest prime factor of $N$.
Are there heuristic arguments showing that no general factoring algorithm can have time complexity $\log N$ or better?