Problem Solving in Automata, Languages, and Complexity

292 COMPUTATIONAL COMPLEXITY

~~ bee-dance ‘2

‘~ bee-dance

111000

r

(p,xxooxx ;O)

Figure 6.4: The ten moves.

Because limn+W t(n)/n = 00, we have that, for sufficiently large n,

n+lk + 10 l t(n)

m

• 
  
  
  
  • 16 < c l t(n).
    m -
  
  
  
  

Thus, A E DTIME(c l t(n)).^0

To get a better understanding of Theorems 6.9 and 6.10, we study some
examples in the following.

Example 6.11 Suppose lim,,, tl(n)/n = 00. If tl(n) = tz(n) for st@-
ciently large n, then DTIME(tl(n)) = DTIME(tz(n)).

Proof. Suppose t 1 (n) = tz(n) for n > no. Then, for n > no, max{n+l, tl(n)}
= max{n+ 1, ta(n)}. Al so, for 1 < 12 < no, there exists a constant c > 1 such
that max{n + 1, tl(n)} 5 c l max(n +?, tz(n)}. Thus, for any n > - 1,

max{n + l,tl(n)} < - c l max{n + 1, ta(n)}.