# Are there any problems whose best known algorithm has run time $O\left(\frac{f(n)}{\log n}\right)$

I've never seen an algorithm with a log in the denominator before, and I'm wondering if there are any actually useful algorithms with this form?

I understand lots of things that might cause a log factor to be multiplied in the run time, e.g. sorting or tree based algorithms, but what could cause you to divide by a log factor?

-
Mergesort, with $f(n) = n\log^2 n$. –  JɛﬀE Feb 3 '13 at 7:06
@JɛﬀE snarky Mcsnarkster –  Suresh Venkat Feb 3 '13 at 7:52
Radix sort - it really is $O(n \log n/ \log n)$. What is going on is that because of the random access, you are able so save a log factor.... –  Sariel Har-Peled Feb 3 '13 at 21:34
I wonder if the DTIME hierarchy theorem, can be used as an argument towards the existence of such algorithms, given that one can do some similar space-cost saving trick in the RAM model. –  chazisop Feb 4 '13 at 10:42

The usual answer to "what could cause you to divide by a log?" is a combination of two things:

1. a model of computation in which constant time arithmetic operations on word-sized integers are allowed, but in which you want to be conservative about how long the words are, so you assume $O(\log n)$ bits per word (because any fewer than that and you couldn't even address all of memory, and also because algorithms that use table lookups would take too much time to set up the tables if the words were longer), and
2. an algorithm that compresses the data by packing bits into words and then operates on the words.

I think there are many examples, but the classic example is the Four Russians Algorithm for longest common subsequences etc. It actually ends up being $O(n^2/\log^2 n)$, because it uses the bit-packing idea but then saves a second log factor using another idea: replacing blocks of $O(\log^2 n)$ bit operations by a single table lookup.

-

The Rubik's Cube is a very natural (and to me, unexpected) example. An $n\times n\times n$ cube requires $\Theta(n^2/\log n)$ steps to solve. (Note that this is theta notation, so that's a tight upper and lower bound).

This is shown in this paper [1].

It may be worth mentioning that the complexity of solving specific instances of the Rubik's cube is open, but conjectured to be NP-hard (discussed here for example). This algorithm guarantees a solution, and it guarantees that all solutions are asymptotically optimal, but it may not solve specific instances optimally. Your definition of useful may or may not apply here, as Rubik's cubes are generally not solved with this algorithm (Kociemba's algorithm is generally used for small cubes as it gives fast, optimal solutions in practice).

[1] Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, Anna Lubiw, and Andrew Winslow. Algorithms for Solving Rubik's Cubes. Proceedings of the 19th Annual European Symposium on Algorithms (ESA 2011), September 5–9, 2011, pages 689–700

-

An example of $\log n$ showing up in the denominator without bit packing tricks is a recent paper by Agarwal, Ben Avraham, Kaplan and Sharir on computing the discrete Fréchet distance between two polygonal chains in time $O(n^2\log\log n/\log n)$. While I'm not familiar with the details of the algorithm, one general trick is to partition the input into relatively small pieces and then combine the answers cleverly (of course this sounds like divide and conquer, but you don't get the log n in the denominator with some clever tricks)

-
This is a more complex instance of the "Four Russians" technique described in David's answer. –  JɛﬀE Feb 3 '13 at 21:00

Not exactly what you asked for, but a situation "in the wild" in which a log factor appears in the denominator is the paper "Pebbles and Branching Programs for Tree Evaluation" by Stephen Cook, Pierre McKenzie, Dustin Wehr, Mark Braverman, and Rahul Santhanam.

The tree evaluation problem (TEP) is: given a $d$-ary tree annotated with values in $\{1,\ldots,k\}$ on the leafs and functions $\{1,\ldots,k\}^d \to \{1,\ldots,k\}$ on internal nodes, evaluate the tree. Here each internal node gets the value of its annotated function on the values of its children. This is an easy problem, and the point is to show that it cannot be solved in logarithmic space (when the height of the tree is part of the input). To that effect, we are interested in the size of branching programs solving TEP.

In Section 5, tight bounds are presented for trees of height 3, both for TEP and for the related problem BEP, in which the output is collapsed to $\{0,1\}$ in some arbitrary way. For TEP the bound is $\Theta(k^{2d-1})$, while for BEP the bound is $\Theta(k^{2d-1}/\log k)$, i.e. you get a saving of $\log k$.

-

Even though it's not about runtime, I thought it worth mentioning the classical result of Hopcroft, Paul, and Valiant: $\mathsf{TIME[t]} \subseteq \mathsf{SPACE}[t/\log t]$ [1], since it's still in the spirit of "what could cause you to save a log factor."

That gives lots of examples of problems whose best known upper bound on space complexity has a log in the denominator. (Depending on your viewpoint, I would think that either makes this example very interesting - what an amazing theorem! - or very uninteresting - it's probably not "actually useful".)

[1] Hopcroft, Paul, and Valiant. On time versus space. J. ACM 24(2):332-337, 1977.

-

There are two problems with tight query complexity $\Theta(n/\log n)$:

-

The best known algorithm for computing the edit (a.k.a. Levenshtein) distance between two strings of length $n$ takes $O((n/\log n)^2)$ time:

William J. Masek, Mike Paterson: A Faster Algorithm Computing String Edit Distances. J. Comput. Syst. Sci. 20(1): 18-31 (1980).

-
Again, this is a variation of the Four Russians algorithm, I think. –  David Eppstein Feb 4 '13 at 5:11

Here's another example of a tight bound having a log factor. (This is Theorem 6.17 from Boolean Function Complexity: Advances and Frontiers by Stasys Jukna.)

The formula size (over the full binary basis or the De Morgan basis) of the element distinctness problem is $\Theta(n^2/\log n)$, where $n$ is the number of bits in the input.

The reason the log factor appears in the denominator is that representing $m$ integers between 1 and $\text{poly}(m)$ requires $n := O(m \log m)$ bits in total, since each integer requires $O(\log m)$ bits. So an upper bound that looks natural in terms of $m$, like $\Theta(m^2 \log m)$, becomes $\Theta(n^2/\log n)$ when expressed in terms of $n$, where $n$ is the number of bits in the input.

-

$\Theta(n/\log n)$ appears as the correct bound for a problem considered by Greg and Paul Valiant (no connection to bit tricks):

Gregory Valiant, and Paul Valiant, The power of linear estimators, 2011. In the 52nd Annual IEEE Symposium on the Foundations of Computer Science, FOCS 2011.

-

Finding the prime factors of n by trial division when the list of primes is already given. There are $\theta(\frac{n}{\log(n)})$ primes less than n so if these primes are given to you, then trial division of n by each of them takes $\theta(\frac{n}{\log(n)})$ time (assuming division is a constant-time operation)

-
In fact, it's enough to look at the roughly $2\sqrt{n}/\log n$ primes below $\sqrt{n}$. But there are far better algorithms out there. –  Yuval Filmus Feb 7 '13 at 5:16

somewhat similar to JG's answer & "thinking outside the box", this seems like a related/relevant/apropos/fundamental negative result. based on diagonalization with a universal TM, there exists a $O(f(n))$ DTIME language that cannot run in $O\left({f(n)\over{\log f(n)}}\right)$ DTIME, due to the time hierarchy theorem. so this applies to a linear DTIME algorithm that exists, $f(n)=n$, that runs impossibly in $O\left(n \over {\log n} \right)$ DTIME.

-
on a TM, $\mathsf{DTIME}(n/\log n)$ is trivial as it doesn't allow the machine to read the whole input. also, the DTIME notation makes the big-oh notation unnecessary. –  Sasho Nikolov Feb 12 '13 at 4:23
?? there is still theory for sublinear time algorithms... –  vzn Feb 12 '13 at 4:51
sublinear algorithms make sense in oracle & random access models. DTIME is standardly defined w.r.t. multitape TM, and that's the definition used in the hierarchy theorem for DTIME. –  Sasho Nikolov Feb 13 '13 at 0:21
No, @SashoNikolov, $\mathsf{DTIME}(n/\log n)$ is not trivial. Compare "Are the first $n/\lg n$ bits of the input all zeros?" with "Do the first $n/\lg n$ bits of the input encode a satisfiable boolean formula?" –  JɛﬀE Feb 13 '13 at 2:06
@JɛﬀE: You cannot test “Are the first $n/\lg n$ bits of the input all zeros?” in $O(n/\log n)$ time on a TM, since you do not know what $n$ is without first reading the whole input, which takes time $n$. It is a standard fact that if $f(n)<n$, then $\mathrm{DTIME}(f(n))$ contains only languages the membership in which can be determined from the first $k$ bits of input for a constant $k$ (and therefore are computable in constant time). –  Emil Jeřábek Feb 13 '13 at 14:12