Analyzing Algorithms Part III
Understand how to calculate and generalize the instruction count for algorithms using summation formulas, and see how these calculations illustrate changes in running time as input size grows. Learn to interpret algorithmic performance beyond exact counts toward Big-O estimation.
We'll cover the following...
We'll cover the following...
Generalizing Instruction Count
Let's try to generalize the running time for an array of size n.
| Code Statement | Cost |
|---|---|
| 1. for (int i = 0; i < input.length; i++) { | executed (2 x n) + 2 times. |
| 2. int key = input[i]; | executed n times |
| 3. int j = i - 1; | executed n times |
| 4. while (j >= 0 && input[j] > key) { | We already calculated the cost of each iteration ... |