- #1
xeon123
- 90
- 0
In the Turing Machine, the machine accepts a word if the computation terminates in the accepting state. The language accepted by the machine, L(M), has associated an alphabet Δ and is defined by
L(M) = {w [itex]\in[/itex] [itex]\Delta[/itex]}
This means that the machine understands the word w if w belongs to the language.
We denote by Tm(w) the number of steps in the computation of M on the input w. If the computation never halts, then Tm(w)=infinity.
Also, we denote the worst case run time of M as
Tm(n) = max{Tm(w)}
which means the biggest words in the dictionary (I suppose).
But, we say that M runs in polynomial time if there exists k such that for all n, T(n)[itex]\leq[/itex] n^k + k.
I don't understand what n^k+k means. Can anyone explain me the last expression?
Thanks,
L(M) = {w [itex]\in[/itex] [itex]\Delta[/itex]}
This means that the machine understands the word w if w belongs to the language.
We denote by Tm(w) the number of steps in the computation of M on the input w. If the computation never halts, then Tm(w)=infinity.
Also, we denote the worst case run time of M as
Tm(n) = max{Tm(w)}
which means the biggest words in the dictionary (I suppose).
But, we say that M runs in polynomial time if there exists k such that for all n, T(n)[itex]\leq[/itex] n^k + k.
I don't understand what n^k+k means. Can anyone explain me the last expression?
Thanks,
Last edited by a moderator: