Understanding this description of NP completeness in TAOCP, Fascicle 6, Satisfiability.

Question

Context

I am reading TAOCP, Vol 4, Fascicle 6, Satisfiability.

I am trying to understand what Donald Knuth is saying here.

Question

Does $N^{O(1)}$ mean that for a formula of size $N$ it will take $N^{m}$ steps where $m$ is some constant like $17$ or $\pi$?

For instance if $N=10$ and $m=17$, then an "efficient" algorithm will take $10^{17}$ steps.

Answer 1

Yes, but note that as usual this formula is for asymptotic only, as $N$ go to infinity.

$N^{O(1)}$ technically mean it's bounded above by a function of the form $N^{f(N)}$ such that $f(N)$ is eventually bounded above by a constant multiple of $1$. Parsing all that, it does mean it's eventually bounded by $N^{m}$ for some constant $m$.