Estimating Running Time of an Algorithm using Simple Rules.
To estimate the running time of an algorithm and the difference of the algorithm against others, we make a strong assumption where the running time of an algorithm is independent of specific hardware. Using this assumption, we can study the efficiency of the algorithms and compare the algorithms to each other, deciding which one is better and finding an optimal solution to a problem.
Following the assumption of hardware independence, the analysis of the running time of an algorithm depends only on the statements defined in the algorithm (i.e., the steps that the algorithms need to follow for solving a specific problem). Since the execution time of the algorithms’ statements is not the same for all of them (i.e., some steps need more time to be executed than others), it is necessary to be defined a set of rules.
Rule 1:
The time required to fetch an integer from memory is defined as tfetch. The time needed to store an integer to the memory is defined as tstore.
For example, the running time of the statement “x = 1” is tfetch + tstore, because the integer is in the memory (typically any constant is stored in memory) and have to be fetched and also this integer has to be stored to the variable “x” which is in memory. The same running time has the statement “x = y” because we want to get the value of the variable “y” which is stored in memory.
Rule 2:
The time needed for each basic operation to be executed is defined as t+, t–, tx, t<, t/. So, the running time of the statement “y = x + 1” is 2tfetch + t+ + tstore. The 2 fetches are for “x” and “1”. The result is stored in variable “y” (tstore). The addition operation time is t+.
Rule 3:
The time needed to a function to be called is defined as tcall while the time required to a function to return a value is defined as treturn.
Rule 4:
The time needed to pass a value as parameter to a function is the same as the time needed to store a value in memory. For example, the running time of “y = f(x)” is 2tstore + tfetch + tcall + Tf(x). Note here that the treturn is part of the function and not of the above statement. Furthermore, the Tf(x) is the total running time of the function “f”.
Rule 5:
The time required for the address calculation implied by an array subscripting operation is defined as t[] . For example, the running time of the statement “y = a[i]” is 3tfetch + tstore +t[]. The fetches are (1) the value of i, (2) the value of a and (3) the value of a[i].
Using these rules, we can easily estimate the running time of the algorithms.
Examples
Here, we present some programs in C++ and we estimate their running time.
2: if ( a > b )
3: return a;
4: return b;
5: }
The running time of the function “max” depends on the lines 2,3 and 4. So, we have to estimate for each line (or step) the corresponding time and then to calculate the total time of the function.
| Lines | a > b | a <= b | Code |
| 3 | 2tfetch + t< | 2tfetch + t< | If (a > b) |
| 4 | treturn + tfetch | – | return a; |
| 5 | – | treturn + tfetch | return b; |
| Total Running Time | 3tfetch + t< + treturn | 3tfetch + t< + treturn |
Making our life better, we define the total time of max function when “a > b” as t1 and the total time of max function when “a <= b” as t2. We can say that Tmax(a,b) = t1 ή Tmax(a,b) = t2. However, as we can see t1 = t2, so the Tmax(a,b) = 3tfetch + t< + treturn. if t1 <> t2, then the total worst running time of the function would be that t with the worst time.
2: int maxNumber = -1;
3: for (int i=0; i<n; i++){
4: maxNumber = max(maxNumber,A[i]);
5: }
6: return maxNumber;
7: }
The function “findMaxNumber” gets as input an array A with n values and returns the maximum number of the array. We also use the previous function “max” to find the maximum number of two variables. The running time of the function depends on the lines 2 to 6.
| Lines | Running Time | Code |
| 2 | tfetch + tstore | int maxNumber = -1; |
| 3a | tfetch + tstore | int i =0; |
| 3b | (2tfetch + t<)*(n+1) | i < n; |
| 3c | (2tfetch + tstore + t+)*n | i++; |
| 4 | (3tstore + tcall + Tmax(a,b) + 4tfetch + t[])*n | maxNumber = max(maxNumber,A[i]); |
| 6 | treturn + tfetch | return maxNumber; |
As we can see in the table, we used the 5 rules defined above to find the running time of the algorithm (Exercise: Find the total running time of the algorithm using also the running time of the function “max”). There are some interesting parts in this source code:
- The line 3 is split into three parts. The initialization of the i variable is executed only one time while the statements 3b and 3c are executed at least n times. The 3b statement is executed n + 1 times because we also take into account when the condition is getting false for the first time.
- To find the running time of the 4th statement we needed all 5 rules. Firstly, we have to fetch the A[i] (as we explained above) and the maxNumber. These two parameters need 2tstore when they are passed to the function. The return value of the function is stored in the maxNumber so we need also a tstore.