Counting Steps¶
The following can be counted as one step in a program:
- Primitive operations:
- Variable assignment
- Arithmetic operation
- Comparison
- Array indexing or pointer reference
- Function call (not counting the data)
- Function return (not counting the data)
Note: Runtime of 1 step is independent on input.
1. for Loop Step Counting
The basic form of a for-loop: for (initialization; test; update)
The initialization is performed once ($1$)
The test is performed every time the body of the loop runs, plus once for when the loop ends ($n + 1$)
The update is performed every time the body of the loop runs ($n$)
Example:
1 int func1(int n) {
2 int sum = 0;
3 for (int = 0; i < n; ++i) {
4 sum += 1;
5 }
6 return sum;
7 }
In the function above, line 2 is an assignment, which takes 1 step.
On line 3, the initialization takes 1 step, the test takes $n + 1$ steps, and the update takes $n$ steps.
On line 4, it is a primitive operation, takes 1 step. On line 6, it is a function return, takes 1 step.
Because the loop body will be implemented $n$ times, the total steps will be $4 + 3n$.
2. Polynomial Step Counting
Example:
1 int func2(int n) {
2 int sum = 0;
3 for (int i = 0; i < n; ++i) {
4 for (int j = 0; j < n; ++j) {
5 ++sum;
6 }
7 }
8 for (int k = 0; k < n; ++k) {
9 --sum;
10 }
11 return sum;
12 }
In the function above, line 2 is an assignment, which takes 1 step.
On line 3, the initialization takes 1 step, the test takes $n + 1$ steps, and the update takes $n$ steps.
On line 4, the initialization takes 1 step, the test takes $n + 1$ steps, and the update takes $n$ steps. However, it is inside another for loop on line 3, so we have to multiply with n when calculating the total steps.
On line 5, it is an arithmetic operation, which takes 1 step. Hoever, it is inside two for loops, so it actually runs $n \times n = n^2$ times in total.
On line 8, the initialization takes 1 step, the test takes $n + 1$ steps, and the update takes $n$ steps.
On line 9, it is an arithmetic operation, which takes 1 step. However, it is inside another for loop on line 9, so we have to multiply with n when calculating the total steps.
On line 11, it is the function return, which takes 1 step.
Adding all these up, we will get the total steps: $1 + (2 + 2n) + (2 + 2n) \times n + n^2 + (2 + 2n) + n + 1 = 3n^2 + 7n + 6$
