Algorithmic Analysis

Introduction

There are two main issues for algorithms that should be addressed, correctness and speed. Correctness is more important than speed because it would not matter how fast an algorithm produces a result if it is not correct. However, it is the goal of the algorithm designer to ensure that the algorithm is both correct and as fast as possible, because even though an algorithm may produce the correct result all of the time, if the result takes many days to obtain with some significant amount of time then it is just about as undesirable as an incorrect algorithm. The following are some ways of ensuring correctness and calculating speed.

Calculating Running Time

Program 1:

 1. unsigned int sum = 0;
 2. 
 3. for (unsigned int i = 0; i < n; i++)
 4. {
 5. sum += n;
 6. }

For program 1 we have at line 1 O(1) or O(c), where c is a constant. The loop at line 3 executes n times for a cost of O(n) and the operational assignment at line 5 is O(1) or O(c). Since a constant plus a constant is another constant we can just use c to represent that resulting constant. For a total time of T(n) = n + c, which means that this simple algorithm runs in O(n) time.

Program 2:

 1. unsigned int sum = 0;
 2. 
 3. for (unsigned int j = 0; j < n; j++)
 4. {
 5. for (unsigned int i = 0; i < j; i++)
 6. {
 7. sum++;
 8. }
 9. }

For program 2, again at line 1 we have O(c). The outer loop at line 3 executes n times for a cost of O(n). Each time the outer executes the inner loop at line 5 executes a specified number of times, namely j times. During the last run of the outer loop the inner loop will execute n times. Finally line 7 is O(c). We then have for a total of T(n) = n * n + c, which means that this algorithm runs in O(n²) time.

Program 3:

 1. unsigned int sum = 0;
 2. 
 3. for (unsigned int k = 0; k < n; k *= 2)
 4. {
 5. for (unsigned int i = 0; i < n; i++)
 6. {
 7. sum++;
 8. }
 9. }

Again at line 1 we have O(c). The outer loop at line 3 actually executes log n times for a cost of O(log n), since in each execution, k is doubled until it reaches n. The inner loop at line 5 executes in O(n). Again, in line 7 sum++ executes in O(c). The total running time for program 3 is T(n) = n * log n + c, which is O(n log n) time.

Program 4:

 1. int RunningTotal(int n)
 2. {
 3. if (n <= 0)
 4. {
 5. return 0;
 6. }
 7. 
 8. return (RunningTotal(n - 1) + n);
 9. }

Calculating the running time for recursive functions is a little more subtle. This program basically adds each (n - 1) until n is 0. For instance if n = 5 this function eventually returns 0 + 1 + 2 + 3 + 4 + 5 = 15. Line 5 runs in constant time O(c) when n = 0. Line 8 runs in T(n - 1) time for n > 0. We then have for a total time of T(n) = T(n - 1) + c, which runs in O(n) time.

Proof of Correctness

Let's use proof by induction to prove the correctness of program 2 above:

 1. unsigned int sum = 0;
 2. 
 3. for (unsigned int j = 0; j < n; j++)
 4. {
 5. for (unsigned int i = 0; i < j; i++)
 6. {
 7. sum++;
 8. }
 9. }

We know that this program's running time is O(n²). It's closed form notation is Σⁿ j = [n (n + 1)] / 2, from j = 1 to n.

For n = 0 we know that this summation is true because Σⁿ j = [0 (0 + 1)] / 2 = 0.
For n = 1 we also know that this summation is true because Σⁿ j = [1 (1 + 1)] / 2 = 1.
So, we need to assume that this is true for n, which is simply Σⁿ j = [n (n + 1)] / 2.

Now we need to show that the case for n + 1 is true:

Σ^{n + 1} j = Σⁿ j + (n + 1)

= [[n (n + 1)] / 2] + (n + 1)

= [(n² + n) / 2] + [(2n + 2) / 2]

= (n² + 3n + 2) / 2

= [(n + 1)(n + 2)] / 2, which checks when you plug n + 1 into [n (n + 1)] / 2.

΢

Links

http://www.nist.gov/dads/HTML/bigOnotation.html
http://www.me.berkeley.edu/~e77/lecnotes/ch20/ch20.htm
http://www.math.sc.edu/~sumner/numbertheory/induction/Induction.html
http://www.cs.cornell.edu/courses/cs312/2001sp/recitation/recitation_09.html