In section 9.4.1 in our textbook, as well as in the following slide, we encountered this definition:

I could not understand why is the length of the CNF formula is O(f(n)^3), where f(n) is the steps for the NTM to decide a string of length n.

Can anyone explain it? Maybe some examples or illustration would be super helpful.

Thanks a bunch!