Skip to main content
3 votes

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, ...
codeR's user avatar
  • 1,467
2 votes

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 ...
gnasher729's user avatar
  • 30.7k
2 votes

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.
JobHunter69's user avatar
2 votes
Accepted

Is the Partition problem polynomial when all integers are large?

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 ...
Shaq's user avatar
  • 148

Only top scored, non community-wiki answers of a minimum length are eligible