-4
$\begingroup$

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?

Thanks in advance.

$\endgroup$
3
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

Sublinear time algorithms are rare "in daily programming" for several reasons. Daily programming involves classic, deterministic, sequential computation on small inputs without strong assumptions on the input structure/distribution and must always return the correct answer. In contrast, sublinear time algorithms are often

In addition to algorithms, many data structures have sublinear time operations (relative to the number of elements currently stored). My two favorites are the

  • 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
  • soft heap, which is a deterministic data structure with all constant time "on average" operations but only has to return items close to the minimum.
| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.