Hartmanis and Sterns [HS65] showed that,
for multi-tape Turing machines,
if 
and both 
and 
are time-constructible,
then 
is a proper subset of 
.
This is the best hierarchy known for deterministic classes
in the worst case.
Average-case hierarchies have been investigated within several
different frameworks. One approach is to study, for
functions and with 
, whether
there is a language in DTIME
such that a very large
portion of instances 
will require time more than 
to compute.
This approach has a long history (e.g.,
see [GGH94]). Among others, the following
result of
Geske, Huynh, and
Seiferas [GHS91] says that for every fully
time-constructible function
there is a set 
such that, for
every function , if 
, then
every Turing machine that accepts 
requires more than
steps for all but finitely many inputs .
It follows that there is an expected time hierarchy that is
independent of distributions and is as tight as the
Hartmanis-Sterns hierarchy for worst-case deterministic time.
In a different approach, Li and
Vitányi [LV92] showed that under the
universal distribution
with probability 
,
where 
is the prefix variant of
Kolmogorov complexity [Gac74], the
expected time of any problem on strings of the same length is
the same as the worst-case complexity on that length.
So under the universal distribution,
any hierarchy results for DTIME(
), however tight,
will also apply to the expected-time complexity classes of time .
This line of research was extended
in
[Mil91][Kob95].
However, the distributions used in these results are
either not computable (e.g., 
),
or require super-polynomial time to compute.