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

Question

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?

Answer 1

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.

Answer 2

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) NP hard [2]. The $\Theta(n^2/\log n)$ 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

[2] Erik D. Demaine, Sarah Eisenstat, and Mikhail Rudoy. Solving the Rubik's Cube Optimally is NP-complete. Proceedings of the 35th International Symposium on Theoretical Aspects of Computer Science (STACS 2018), February 28–March 3, 2018, pages 24:1-24:13.

Answer 3

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)

Answer 4

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$.

Answer 5

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

• Coin weighing problem with spring scale.
• Mastermind with n position and 2 colors.

Answer 6

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.

Answer 7

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).

Answer 8

$\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.

Answer 9

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.

Answer 10

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)

Answer 11

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.