ANALYSIS OF for LOOPS
THEORY OF ALGORITHMS
General Principles
Count all operations (separated by types)
3 multiplications
1 // evaluate quadratic function
2
2 additions 3
double eval ( double a , double b ,
double c , double x )
4 {
1 assignment 5
6 double ans = a*x*x + b*x + c;
Runtime = 3c∗ + 2c+ + c= 7 return ans ;
8 }
cop is the cost of an op
2
Always take the worst case, eg. in an if statement
1 int f(int n)
2 {
3 if (n % 2 == 0)
4 return n / 2;
5 else
6 return (3 * n + 1) / 2;
7 }
Worst-case runtime: c% + c== + c∗ + c+ + c/
3
In practice: count only one type of operation
1 int f(int n)
2 {
3 if (n % 2 == 0)
4 return n / 2;
5 else
6 return (3 * n + 1) / 2;
7 }
Runtime is proportional to c/ . We choose / because it is the most
expensive operation in this algorithm
We usually express the running time as the number of operations
being counted. In this case, the running time is 1 (division).
4
Analyzing for loops
Count ans < V[i]
1 // return largest element
2 string maxel (const vector<string> & V)
3 {
4 int n = [Link]();
5 assert(n > 0);
6 string ans(V[0]);
7
8 for (int i = 1; i < n; ++i)
9 if (ans < V[i])
10 ans = V[i];
11
12 return ans;
13 }
The answer is not 1 because the operation ans < V[i] is
performed multiple times.
We need to count the number of loop iterations
5
Rewrite for loop as summation
last
1 for ( int i = first; i <= last; ++ i ) X
2 body; (1) = last − first + 1
i=first
6
Count ans < V[i]
1 // return largest element
2 string maxel (const vector<string> & V)
3 {
4 int n = [Link]();
5 assert(n > 0);
6 string ans(V[0]);
7
8 for (int i = 1; i < n; ++i)
9 if (ans < V[i])
10 ans = V[i];
11
12 return ans;
13 }
n−1
X
(1) = (n − 1) − 1 + 1 = n − 1.
i=1
7
Practice
merge: count A[i] < A[j]
1 void merge(string A[], int lo, int m, int hi)
2 {
3 assert (lo <= m && m <= hi);
4 int i(lo), j(m+1), k, n(hi-lo+1), B[n];
5
6 for (k = 0; k < n; ++k)
7 {
8 if (j > hi)
9 B[k] = A[i++];
10 else if (i > m)
11 B[k] = A[j++];
12 else if (A[i] < A[j])
13 B[k] = A[i++];
14 else
15 B[k] = A[j++];
16 }
17 copy(B, B+n, A+lo);
18 }
8
n−2
X
(1) = (n − 2) − 0 + 1
k=0
= n − 1.
Why n−2 ?
9
Nested for loops
1 sum = 0;
2 for (int i = 0; i < n; ++i)
3 for (int j = 0; j < n; ++j)
4 sum = sum + i + j;
10
1 sum = 0;
2 for (int i = 0; i < n; ++i)
3 for (int j = 0; j < n; ++j)
4 sum = sum + i + j;
n−1X
X n−1 n−1 X
X n−1
(2) = 2 (1)
i=0 j=0 i=0 j=0
n−1
X
= 2 (n − 1 − 0 + 1)
i=0
n−1
X
= 2 (n)
i=0
n−1
X
= 2n (1)
i=0
2
= 2n
11
An Important Identity
n
X
(i) = 1 + 2 + 3··· + n
i=1
n(n + 1)
=
2
12
Insertion Sort: count V[j] < V[j-1]
1 void insertion_sort(vector<string> & V)
2 {
3 int n = [Link]();
4 for (int i = 1; i < n; ++i)
5 for (int j = i; j > 0 && V[j] < V[j-1]; --j)
6 swap(V[j], V[j-1]);
7 }
13
1 void insertion_sort(vector<string> & V)
2 {
3 int n = [Link]();
4 for (int i = 1; i < n; ++i)
5 for (int j = i; j > 0 && V[j] < V[j-1]; --j)
6 swap(V[j], V[j-1]);
7 }
n−1X
X 1 n−1 X
X i
(1) = (1)
i=1 j=i i=1 j=1
n−1
X
= (i − 1 + 1)
i=1
n−1
X
= (i)
i=1
(n − 1)n
=
2
14
What about the number of swaps made by insertion sort ?
15
Selection Sort: count array element comparisons / swaps
1 void selection_sort(vector<string> & V)
2 {
3 int n = [Link]();
4 for (int s = n; s > 1; --s)
5 {
6 int mi(0);
7 for (int i = 1; i < s; ++i)
8 if (V[mi] < V[i])
9 mi = i;
10 swap(V[mi], V[s-1]);
11 }
12 }
16