CmSc 250 Intro to Algorithms | ||||||||||||||||||||||
Running Time Calculations
An algorithm to solve a particular task employs some set of
basic operations. Typical basic operations for some problems are the following:
The work done by an algorithm, i.e. its complexity, is determined by the number of the basic operations necessary to solve the problem. Note: The complexity of a program that implements an algorithm is roughly
the same,
Some algorithms are not dependent on the size of the input - the number of the operations they perform is fixed. Other algorithms depend on the size of the input, and these are the algorithms that might cause problems. Before implementing such an algorithm, we have to be sure that the algorithm will finish the job in reasonable time. What is size of input? We need to choose some reasonable measure of size. Here are some examples:
The core of the algorithm analysis : to find out how the number of the
basic operations Rule 1: for loops The running time of a for loop is at most the running time of
the statements inside the loop for( i = 0; i < n; i++)
The statements in the loop heading have fixed number of operations, hence they have constant running time O(1) when executed only once. The statement in the loop body has fixed number of operations, hence it has a constant running time when executed only once. for( i = 0; i < n; i++) // i = 0; executed only once: O(1) // i < n; n + 1 times O(n) // i++ n times O(n) // total time of the loop heading: // O(1) + O(n) + O(n) = O(n) sum = sum + i; // executed n times, O(n) The loop heading plus the loop body will give: O(n) + O(n) = O(n). Hence we can say: Rule 2: Nested loops The total running time is the running time of the inside statements times the product of the sizes of all the loops sum = 0;for( i = 0; i < n; i++) sum++; Applying Rule 1 for the nested loop (the 'j' loop) we get O(n) for the body of the outer loop. The outer loop runs n times, therefore the total time
for the nested loops will be What happens if the inner loop does not start from 0? sum = 0;for( i = 0; i < n; i++) sum++; Here, the number of the times the inner loop is executed depends on the value of i: i = 0, inner loop runs n times i = 1, inner loop runs (n-1) times i = 2, inner loop runs (n-2) times ... i = n - 2, inner loop runs 2 times i = n - 1, inner loop runs 1 (once) Adding the right column, we get: ( 1 + 2 + … + n) = n*(n+1)/2 = O(n^{2}) General rule for loops: Running time is the product of the size of the loops times the running time of the body. Example: for( i = 0; i < n; i++) sum++; We have one operation inside the loops, and the product of the sizes
is 2n^{2}. Rule 3: Consecutive program fragments The total running time is the maximum of the running time of the individual fragments sum = 0;
sum = 0; sum++; The first loop runs in O(n) time, the second - O(n^{2}) time, the maximum is O(n^{2}) Rule 4: If statement if Condition The running time is the maximum of the running times of S1 and S2.
for (i = 0; i < n; i++) if (a[i] == x) return 1; // 1 means succeed return -1; // -1 means failure, the element is // not found The basic operation in this problem is comparison, so we are interested in how the number of comparisons depends on n. Here we have a loop that runs at most n times: If the element is at the end, we need n comparisons. If the element is somewhere in between, we need less than n comparisons. In the worst case (element not there, or located at the end), we have n comparisons to make. Hence the number of operations is O(n). To find what is the average case, we have to consider
the possible cases: element is at the second position: 2 comparisons etc. We compute the sum of the comparisons for the possible cases and then divide by the number of the cases, assuming that all cases are equally likely to happen: 1 + 2 + … + n = n(n+1)/2 Thus in the average case the number of comparisons would be (n+1)/2 = O(n). Generally, the algorithm for finding an element in an unsorted array needs O(n) operations. for (i = 0; i < n; i++) for (j = 0; j < m; j++) if (a[i][j] == x) return 1 ; // 1 means succeed return -1; // -1 means failure - the element // is not found. Here the inner loop runs at most m times and it is located
in another loop that runs at most n times,
so in total there would be at most nm operations.
Strictly speaking, nm is less than n^{2} when m < n.
However, for very large values of n and m the difference is
negligible, amax = a[0]; for (i = 1; i < n; i++) if (a[i] > amax) amax = a[i]; Here the number of operations is always n-1. The amount of work depends on the size of the input, but does not depend on the particular values. The running time is O(n), we disregard "-1" because the difference for large n is negligible.The complexity here is O(n), we disregard "-1" because the difference for large n is negligible.
Exam-like questions and problems with solutions
| ||||||||||||||||||||||
Back to Contents page Created by Lydia Sinapova |