Analyzing Algorithms Part III
In this lesson, we will work out a generalization for the number of instructions executed for an array of length n
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 of the inner loop. We sum up the costs across all the iterations. Note that the inner loop will be executed n times and each execution will result in (iterations x 7)+2 instructions being executed. And the number of iterations will successively increase from 0, 1, 2 all the way up to(n-1). See the dry run in the previous lesson to convince yourself of the validity of this result. |
5. Inner loop statments | [(0 x 7) + 2] + [(1 x 7) + 2] + [(2 x 7) + 2] + ... [( (n-1) x 7) + 2] = 2n + 7 * [ 0 + 1 + 2 + ... (n-1) ] = 2n + 7 [ n(n-1)⁄2 ] |
11. } //inner loop ends |
12. } |
If we use the above formulas and apply an array of size 5 to them, then the cost should match with what we calculated earlier.
Summation of Series
We glossed over how we converted the sum of the series 0 + 1 + 2 ...(n-1) to n(n-1)⁄2? However, even though we promised to steer clear of complicated mathematics as much as possible, this is one of the cardinal summations that you must know. Without a formal proof, remember that the sum of the first k natural numbers can be represented as:
If you add the first 5 natural numbers the sum is:
However, our summation sums up to n-1 and includes a zero. We can drop the zero because adding zero to anything yields the same value. We know:
We subtract k on both sides of the equation to get:
Coming across this summation is very common in algorithmic analysis and, without getting too technical, if you can identify this series, then you know how to apply a formula to sum it up.
Level up your interview prep. Join Educative to access 80+ hands-on prep courses.