# Tag Info

### What does "computer steps" mean in this runtime definition?

In runtime analysis, we usually define something called a basic operation that can be executed in constant time under the assumed computation model. Since we are going to do an asymptotic analysis, ...
• 1,467

### What does "computer steps" mean in this runtime definition?

“Computer steps” has intentionally no precise definition. This is usually about execution time, and we assume that every computer has a constant time T, which is different for every computer, and each ...
• 30.7k

### How is the prefix function (for KMP) time complexity O(N)?

I figured it out. j never goes negative and it increases by at most n times. Thus the while loop (which always decreases j) will run a lifetime total of not more than n times.
• 324
Yes. I think it is easier to look at your constrain from the other way around. Given the input in size $n$, you allow it to be legal only if there are at most $log(n)$ numbers. For $log(n)$ numbers ...