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

<p>This is shown in <a href="http://erikdemaine.org/papers/Rubik_ESA2011/" rel="nofollow noreferrer">this paper</a> [1].</p>

<p>It may be worth mentioning that the complexity of solving specific instances of the Rubik's cube is <s>open, but conjectured to be NP-hard (discussed <a href="https://cstheory.stackexchange.com/questions/783/is-optimally-solving-the-nnn-rubiks-cube-np-hard">here</a> for example)</s> <a href="https://arxiv.org/pdf/1706.06708.pdf" rel="nofollow noreferrer">NP hard</a> [2]. The <span class="math-container">$\Theta(n^2/\log n)$</span> 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 (<a href="http://kociemba.org/cube.htm" rel="nofollow noreferrer">Kociemba's algorithm</a> is generally used for small cubes as it gives fast, optimal solutions in practice).</p>

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

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

CC BY-SA 4.0
2013-02-03T03:56:46.713Z
2019-09-03T14:47:13.437Z
2019-09-03T14:47:13.437Z
SamM
<p>An example of $\log n$ showing up in the denominator without bit packing tricks is a recent paper by <a href="http://arxiv.org/abs/1204.5333">Agarwal, Ben Avraham, Kaplan and Sharir</a> 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)</p>

CC BY-SA 3.0
2013-02-03T21:00:42.027Z
This is a more complex instance of the "Four Russians" technique described in David's answer.
Jeffε
CC BY-SA 3.0
2013-02-03T08:00:27.923Z
2013-02-03T08:00:27.923Z
Suresh Venkat
<p>There are two problems with tight query complexity $\Theta(n/\log n)$:</p>

<ul>
<li><a href="http://www.cs.mcgill.ca/~colt2009/papers/004.pdf">Coin weighing problem with spring scale.</a> </li>
<li><a href="http://www.mpi-inf.mpg.de/~winzen/Mastermind.pdf">Mastermind with n position and 2 colors.</a></li>
</ul>

CC BY-SA 3.0
2013-02-05T20:44:22.867Z
2013-02-05T20:44:22.867Z
Thatchaphol
<p>Not exactly what you asked for, but a situation "in the wild" in which a log factor appears in the denominator is the paper "<a href="http://arxiv.org/abs/1005.2642">Pebbles and Branching Programs for Tree Evaluation</a>" by Stephen Cook, Pierre McKenzie, Dustin Wehr, Mark Braverman, and Rahul Santhanam.</p>

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

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

CC BY-SA 3.0
2013-02-03T03:20:06.360Z
2013-02-03T17:03:03.297Z
2013-02-03T17:03:03.297Z
Yuval Filmus
<p>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 <em>save</em> a log factor." </p>

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

<p>[1] Hopcroft, Paul, and Valiant. <a href="http://dx.doi.org/10.1145/322003.322015">On time versus space</a>. J. ACM 24(2):332-337, 1977.</p>

CC BY-SA 3.0
2013-02-04T21:36:58.760Z
2013-02-04T21:46:32.743Z
2013-02-04T21:46:32.743Z
Joshua Grochow
<p>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:</p>

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

CC BY-SA 3.0
2013-02-04T05:11:38.703Z
Again, this is a variation of the Four Russians algorithm, I think.
David Eppstein
CC BY-SA 3.0
2013-02-03T22:51:57.163Z
2013-02-03T22:51:57.163Z
Mahdi Cheraghchi
<p>$\Theta(n/\log n)$ appears as the correct bound for a problem considered by Greg and Paul Valiant (no connection to bit tricks):</p>

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

CC BY-SA 3.0
2013-02-12T22:33:33.400Z
2013-02-12T22:33:33.400Z
Jelani Nelson
<p>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.)</p>

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

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

CC BY-SA 3.0
2013-02-17T03:55:31.733Z
2013-02-17T03:55:31.733Z
Robin Kothari
<p>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)</p>

CC BY-SA 3.0
2013-02-07T05:16:34.320Z
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
CC BY-SA 3.0
2013-02-07T01:22:19.157Z
2013-02-07T01:22:19.157Z
dspyz
<p>somewhat similar to JG's answer &amp; "thinking outside the box", this seems like a related/relevant/apropos/fundamental <em>negative</em> 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 <a href="http://en.wikipedia.org/wiki/Time_hierarchy_theorem" rel="nofollow">time hierarchy theorem</a>. 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.</p>

CC BY-SA 3.0
2013-02-12T04:23:17.700Z
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
CC BY-SA 3.0
2013-02-12T04:51:02.203Z
?? there is still theory for [sublinear time algorithms](http://en.wikipedia.org/wiki/Time_complexity#Sub-linear_time)...
vzn
CC BY-SA 3.0
2013-02-13T00:21:53.663Z
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
CC BY-SA 3.0
2013-02-13T02:06:58.763Z
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?"
Jeffε
CC BY-SA 3.0
2013-02-13T02:18:07.887Z
@JɛﬀE Fair enough, I was lazy to be more careful in my statement. The issue is that a "hierarchy" is trivial once you reach sublinear DTIME. I.e.  $\mathsf{DTIME}(f(n))$ for $f(n) = o(n)$ is *very easily* seen to be a strict subset of $\mathsf{DTIME}(n)$. Take "is the $n$-th bit of the input 1?"
Sasho Nikolov
CC BY-SA 3.0
2013-02-13T03:53:17.667Z
hi guys after further study admit/concede its not so simple & something is not quite right with the above idea based on other formulations of the time hierarchy theorem other than wikipedia, which doesnt make it clear theres a lower bound on languages where it is applicable, and the other formulations make the restriction more clear eg [here](http://www.cs.duke.edu/~reif/courses/complectures/Arora/lec3.pdf). however, suspect there might exist some language with complexity that approaches (but still exceeds) a linear bound "from above" for which the above idea fits...."exercise for reader" =)
vzn
CC BY-SA 3.0
2013-02-13T14:12:23.600Z
@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
CC BY-SA 3.0
2013-02-13T16:28:03.030Z
fyi wikipedia says that $f(n)$ in the time hierarchy thm need only by [time constructible](http://en.wikipedia.org/wiki/Constructible_function) & then gives two defns of time constructible. at the end, "No function which is o(n) can be time-constructible unless it is eventually constant, since there is insufficient time to read the entire input." so maybe this all amts to some undergraduate exercise or test question... heres another idea, what if the length of the input is specified in binary at the beginning of the input?
vzn
CC BY-SA 3.0
2013-02-13T17:43:07.973Z
new/fixed/similar idea, let $f(n)=e^{\log n}$ and then a DTIME($f(n)$) language exists that is not recognizable in DTIME$\left( e^{\log n} \over \log n \right)$.
vzn
CC BY-SA 3.0
2013-02-14T16:30:40.337Z
and speaking of the time hiearchy thm, this observation is related. define $f(n)$ as in the original question. then there exists a language that can be recognized in $O\left( f(n) \over {\log n} \right)$ but not in $O\left( f(n) \over (\log n)^2 \right)$ for _all_ (time constructible) $f(n)$ such that $f(n) \over (\log n)^2$ is $\omega(n)$.
vzn
CC BY-SA 3.0
2013-02-12T00:53:57.103Z
2013-02-12T02:13:48.653Z
2013-02-12T02:13:48.653Z
vzn
<p>The usual answer to "what could cause you to divide by a log?" is a combination of two things:</p>

<ol>
<li>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</li>
<li>an algorithm that compresses the data by packing bits into words and then operates on the words.</li>
</ol>

<p>I think there are many examples, but the classic example is the <a href="http://en.wikipedia.org/wiki/Method_of_Four_Russians">Four Russians Algorithm</a>
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.</p>

CC BY-SA 3.0
2013-02-03T05:44:44.923Z
2014-04-15T18:55:45.297Z
2014-04-15T18:55:45.297Z
David Eppstein
<p>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?  </p>

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

CC BY-SA 3.0
2013-02-03T07:06:52.187Z
Mergesort, with $f(n) = n\log^2 n$.
Jeffε
CC BY-SA 3.0
2013-02-03T07:52:48.690Z
@JɛﬀE snarky Mcsnarkster
Suresh Venkat
CC BY-SA 3.0
2013-02-03T21:34:51.887Z
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
CC BY-SA 3.0
2013-02-04T10:42:40.983Z
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
<ds.algorithms><big-list><time-complexity>
Are there any problems whose best known algorithm has run time $O\left(\frac{f(n)}{\log n}\right)$
Mike Izbicki
# Are there any problems whose best known algorithm has run time $O\left(\frac{f(n)}{\log n}\right)$

(Asked by: username_0 on 2013-02-03)

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?

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

> **Comments:**
> **username_1**: Mergesort, with $f(n) = n\log^2 n$.  
> **username_2**: @JɛﬀE snarky Mcsnarkster  
> **username_3**: 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....  
> **username_4**: 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.  

---

## 11 answers

### Answer by username_10 on 2013-02-03. Score: 41 | Accepted answer

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](http://en.wikipedia.org/wiki/Method_of_Four_Russians)
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 by username_5 on 2013-02-03. Score: 35

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](http://erikdemaine.org/papers/Rubik_ESA2011/) [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](https://cstheory.stackexchange.com/questions/783/is-optimally-solving-the-nnn-rubiks-cube-np-hard) for example)~~ [NP hard](https://arxiv.org/pdf/1706.06708.pdf) [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](http://kociemba.org/cube.htm) 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 by username_2 on 2013-02-03. Score: 16

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](http://arxiv.org/abs/1204.5333) 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)

> **Comments:**
> **username_1**: This is a more complex instance of the "Four Russians" technique described in David's answer.  

---

### Answer by username_6 on 2013-02-05. Score: 13

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

* [Coin weighing problem with spring scale.](http://www.cs.mcgill.ca/~colt2009/papers/004.pdf)
* [Mastermind with n position and 2 colors.](http://www.mpi-inf.mpg.de/~winzen/Mastermind.pdf)


---

### Answer by username_7 on 2013-02-03. Score: 13

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](http://arxiv.org/abs/1005.2642)" 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 by username_8 on 2013-02-04. Score: 12

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](http://dx.doi.org/10.1145/322003.322015). J. ACM 24(2):332-337, 1977.


---

### Answer by username_9 on 2013-02-03. Score: 8

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

> **Comments:**
> **username_10**: Again, this is a variation of the Four Russians algorithm, I think.  

---

### Answer by username_11 on 2013-02-12. Score: 7

$\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 by username_12 on 2013-02-17. Score: 7

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 by username_13 on 2013-02-07. Score: 2

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)

> **Comments:**
> **username_7**: 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.  

---

### Answer by username_14 on 2013-02-12. Score: -2

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](http://en.wikipedia.org/wiki/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.

> **Comments:**
> **username_15**: 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.  
> **username_14**: ?? there is still theory for [sublinear time algorithms](http://en.wikipedia.org/wiki/Time_complexity#Sub-linear_time)...  
> **username_15**: 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.  
> **username_1**: 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?"  
> **username_15**: @JɛﬀE Fair enough, I was lazy to be more careful in my statement. The issue is that a "hierarchy" is trivial once you reach sublinear DTIME. I.e.  $\mathsf{DTIME}(f(n))$ for $f(n) = o(n)$ is *very easily* seen to be a strict subset of $\mathsf{DTIME}(n)$. Take "is the $n$-th bit of the input 1?"  
> **username_14**: hi guys after further study admit/concede its not so simple & something is not quite right with the above idea based on other formulations of the time hierarchy theorem other than wikipedia, which doesnt make it clear theres a lower bound on languages where it is applicable, and the other formulations make the restriction more clear eg [here](http://www.cs.duke.edu/~reif/courses/complectures/Arora/lec3.pdf). however, suspect there might exist some language with complexity that approaches (but still exceeds) a linear bound "from above" for which the above idea fits...."exercise for reader" =)  
> **username_16**: @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).  
> **username_14**: fyi wikipedia says that $f(n)$ in the time hierarchy thm need only by [time constructible](http://en.wikipedia.org/wiki/Constructible_function) & then gives two defns of time constructible. at the end, "No function which is o(n) can be time-constructible unless it is eventually constant, since there is insufficient time to read the entire input." so maybe this all amts to some undergraduate exercise or test question... heres another idea, what if the length of the input is specified in binary at the beginning of the input?  
> **username_14**: new/fixed/similar idea, let $f(n)=e^{\log n}$ and then a DTIME($f(n)$) language exists that is not recognizable in DTIME$\left( e^{\log n} \over \log n \right)$.  
> **username_14**: and speaking of the time hiearchy thm, this observation is related. define $f(n)$ as in the original question. then there exists a language that can be recognized in $O\left( f(n) \over {\log n} \right)$ but not in $O\left( f(n) \over (\log n)^2 \right)$ for _all_ (time constructible) $f(n)$ such that $f(n) \over (\log n)^2$ is $\omega(n)$.  

---

