<p>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. </p>

<p>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. </p>

<p>The <a href="http://en.wikipedia.org/wiki/Van_Emde_Boas_tree" rel="nofollow">Van Emde Boas data structure</a> can do search in time $O(\log \log U)$ where $U$ is the size of the universe. </p>

CC BY-SA 3.0
2011-06-05T20:50:52.133Z
2011-06-05T20:50:52.133Z
Suresh Venkat
<p><a href="http://en.wikipedia.org/wiki/Time_complexity#Sub-linear_time" rel="nofollow">Sublinear time algorithms</a> 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</p>

<ul>
<li><a href="http://en.wikipedia.org/wiki/Quantum_algorithm" rel="nofollow">quantum</a> (such as <a href="http://en.wikipedia.org/wiki/Grover%27s_algorithm" rel="nofollow">Grover's algorithms</a>),</li>
<li><a href="http://en.wikipedia.org/wiki/Parallel_algorithm" rel="nofollow">parallel</a> (such as <a href="http://en.wikipedia.org/wiki/Bitonic_sorter" rel="nofollow">bitonic mergesort</a>),</li>
<li>an <a href="http://en.wikipedia.org/wiki/Approximation_algorithm" rel="nofollow">approximation</a> (for such problems as <a href="http://www.google.com/search?&amp;q=sublinear%20time%20approximation%20algorithms" rel="nofollow">vertex cover and bin packing</a>),</li>
<li><a href="http://en.wikipedia.org/wiki/Randomized_algorithm" rel="nofollow">randomized</a> with a small chance of failure/error (such as <a href="http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/SW86/SW86.pdf" rel="nofollow">evaluating a balanced NAND tree</a> or algorithms for <a href="http://en.wikipedia.org/wiki/Property_testing" rel="nofollow">property testing</a> when the input is exceedingly large), or</li>
<li>using strong assumptions about input structure/distribution (such as binary search).</li>
</ul>

<p>In addition to algorithms, many <a href="http://en.wikipedia.org/wiki/Data_structure" rel="nofollow">data structures</a> have sublinear time operations (relative to the number of elements currently stored). My two favorites are the</p>

<ul>
<li><a href="http://en.wikipedia.org/wiki/Disjoint-set_data_structure" rel="nofollow">union-find data structure</a>, which, as Suresh Venkat already mentioned, takes "on average" $\alpha(n)$ time for both the <em>union</em> and <em>find</em> operations (where $\alpha(n)$ is one version of an inverse <a href="http://en.wikipedia.org/wiki/Ackermann_function" rel="nofollow">Ackermann function</a>), and the</li>
<li><a href="http://en.wikipedia.org/wiki/Soft_heap" rel="nofollow">soft heap</a>, which is a deterministic data structure with all constant time "on average" operations but only has to return items close to the minimum.</li>
</ul>

CC BY-SA 3.0
2011-06-08T20:02:02.123Z
2014-12-10T07:33:49.170Z
2014-12-10T07:33:49.170Z
Tyson Williams
<p>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).</p>

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

<p>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?</p>

<p>Thanks in advance.</p>

<ds.algorithms><time-complexity>
Examples of uncommon problems with different asymptotic costs?
Gabriel
# Examples of uncommon problems with different asymptotic costs?

(Asked by: username_0 on 2011-06-05)

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.

**Tags:** ds.algorithms, time-complexity

---

## 2 answers

### Answer by username_1 on 2011-06-05. Score: 3

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](http://en.wikipedia.org/wiki/Van_Emde_Boas_tree) can do search in time $O(\log \log U)$ where $U$ is the size of the universe.


---

### Answer by username_2 on 2011-06-08. Score: 0

[Sublinear time algorithms](http://en.wikipedia.org/wiki/Time_complexity#Sub-linear_time) 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

* [quantum](http://en.wikipedia.org/wiki/Quantum_algorithm) (such as [Grover's algorithms](http://en.wikipedia.org/wiki/Grover%27s_algorithm)),
* [parallel](http://en.wikipedia.org/wiki/Parallel_algorithm) (such as [bitonic mergesort](http://en.wikipedia.org/wiki/Bitonic_sorter)),
* an [approximation](http://en.wikipedia.org/wiki/Approximation_algorithm) (for such problems as [vertex cover and bin packing](http://www.google.com/search?&q=sublinear%20time%20approximation%20algorithms)),
* [randomized](http://en.wikipedia.org/wiki/Randomized_algorithm) with a small chance of failure/error (such as [evaluating a balanced NAND tree](http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/SW86/SW86.pdf) or algorithms for [property testing](http://en.wikipedia.org/wiki/Property_testing) when the input is exceedingly large), or
* using strong assumptions about input structure/distribution (such as binary search).

In addition to algorithms, many [data structures](http://en.wikipedia.org/wiki/Data_structure) have sublinear time operations (relative to the number of elements currently stored). My two favorites are the

* [union-find data structure](http://en.wikipedia.org/wiki/Disjoint-set_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](http://en.wikipedia.org/wiki/Ackermann_function)), and the
* [soft heap](http://en.wikipedia.org/wiki/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.


---

