Comp Sci Why is NTM Time Complexity Guessing Polynomial?

[CGandC]

Homework Statement

Not homework but something I don't understand: Why is the time-complexity of $N_1$ below not exponential due to the overhead of going over all possible configurations?

Relevant Equations

NTM = nondeterministic Turing machine

Running time of a nondeterministic Turing machine that is a decider is the depth of its configuration tree ( the length of the longest branch in the tree ).

( Source: Introduction to the theory of computation, Michael Sipser, 3rd edition )

I know the computation of a non-deterministic Turing machine ( NTM ) which is a decider is defined to be the depth of its configuration tree.

In the above example of showing that $HAMPATH \in NP$, where it's highlighted in red - I understand that choosing a specific list of nodes costs polynomial time which is the depth of the configuration tree. However, we seem to be choosing every possible option for a list of $m$ vertices, thus, we have at least $O(m^m)$ configurations to check, so why is the running time of $N_1$ polynomial? shouldn't it be exponential?

 

[pbuk]

Why is the time-complexity of $N_1$ below not[corrected] exponential due to the overhead of going over all possible configurations?

Because it is an NTM: there is no overhead in branching to any finite number of configurations. Alternatively we can imagine that it can "luckily" choose any configuration that leads to acceptance.

 

[CGandC]

I understand now, thanks.