Are there any problems where there is no smallest time complexity, so there is a big-$\mathcal{O}$ but no big-$\Theta$?
More formally, I am looking for any problem $p$ where
- for any algorithm that solves $p$ in time $f(n)$
- there provably exists another algorithm that solves $p$ in time $g(n)$
- where $g(n) = o(f(n))$.
An example would be a problem for which there exist algorithms of complexity $\mathcal{O}(n^k)$ for all $k > 0$, but for which there is no algorithm of lower complexity, like $\mathcal{O}(1)$ or $\mathcal{O}(\log n)$.