# Examples of uncommon problems with different asymptotic costs?

I've being studying some topics of Discrete Mathematics, and I found only a few examples of problems with uncommon asymptotic costs, like Θ(sqrt(n)) or Θ(log(n)) beyond the obvious ones (binary search, for example).

In daily programming, it's common to find linear problems to solve. Doing something to every element of a list, for example.

I can't think in any problems like these that costs sqrt(n) or more examples of Θ(log(n)). Also, I never saw an algorithm with Θ(log(log(n))) time complexity. Can you give me some examples?

A very old algorithm for integer multiplication due to Karatsuba runs in time $O(n^{\log_2 3})$ which is roughly $n^{1.58}$. It's also a very natural algorithm.
If you want something sublinear, then the classic union-find data structure takes "on average" $\alpha(n)$ time to process an update, where $\alpha(n)$ is one version of an inverse Ackermann function. Again, a very natural algorithm.
The Van Emde Boas data structure can do search in time $O(\log \log U)$ where $U$ is the size of the universe.
• union-find data structure, which, as Suresh Venkat already mentioned, takes "on average" $\alpha(n)$ time for both the union and find operations (where $\alpha(n)$ is one version of an inverse Ackermann function), and the