Operation Counting
Here's that example again:
bool lowerHalf(float x, const float* arr, size_t arrSize) { // 1
size_t numLessThan = 0; // 2
for (size_t i = 0; i < arrSize; ++i) { // 3
if (arr[i] < x) { // 4
++numLessThan; // 5
} // 6
} // 7
return numLessThan < arrSize/2.0; // 8
} // 9
Instead of counting instructions, we could abstract away the CPU entirely and focus on the operations we can see in the algorithm.
Which operations should we count?
That's the question! We need to pick, depending on what we want to know or what comparisons we want to make.
For this algorithm, it probably isn't very interesting to count the number of divisions, which is just one no matter what. The things we might be more interested in are increments, less–than comparisons, assignments, and indexing operations. Let's try counting the number of less–than comparisons.
How many less–than comparisons happen when this code runs?
Hay, wait. What do you mean, “How many?” It's not like a number. It depends on the size of the array!
-
Oh, you're right! We need to make another decision.
Typically, the number of operations that are executed depends on the input in some way!
We want to derive a function \( \mathrm{C} \) for the cost of some quantity from the input \( n \) such that \( \mathrm{C}(n) \) gives us the number of operations performed for that input.
To make this analysis concrete/viable, we need to make some decisions:
- What operation or operations are we counting? That is, what are the units of the output of \( \mathrm{C}(n) \)?
- What quantity \( n \) will represent the input in our characterization of the cost?
Example 1
Let's let
- \( n \) be the number of elements in the array, and
- \( \mathrm{C}_{\mathrm{lessthan}}(n) \) be the number of less–than comparisons the algorithm performs.
Looking back at our code, we can see that…
| Line(s) | |
|---|---|
| 1, 2 | There are no comparisons on lines 1 and 2. |
| 3–7 | Define a loop, which is run \( n \) times. |
In each iteration of the loop, we can see there are two less–than comparisons (one for the loop variable, and one between x and arr[i]). |
|
| Then, to end the loop, the last value of the loop variable has to be compared to the loop limit and fail the comparison, so that's one more less–than. | |
| So, we can express the number of comparisons in the loop as \( 1 + \sum^{n}_{i=1}2 = 2n + 1 \). | |
| 8 | Finally, on line 8 we have one last less–than comparison. |
| So the total number of less–than comparisons is \( \mathrm{C}_{\mathrm{lessthan}}( n ) = 2n + 2 \), where \( n \) is the size of the array. |
-
In our working here, we used summation notation. If you're not sure how that works, the video below may help.
Oooooh, math makes me nervous.
-
That's okay; we got you. In this video we'll walk through this analysis.
-
If you are feeling comfortable with the above argument, you can skip this next video.
Example 2
This time, let's let
- \( n \) be the number of bits representing the array and all three input parameters, and
- \( \mathrm{C}_{\mathrm{index}}(n) \) be the number of indexing operations the algorithm performs.
(We will assume for this analysis that float and size_t have 32 bits and float* has 64 bits).
Once again, looking at our code,
| Line(s) | |
|---|---|
| 1, 2 | There are no array-indexing operations. |
| 3–7 | A loop that runs arrSize times. |
| In each iteration of the loop, we can see there is a single indexing operation. | |
| So we can express the number of comparisons in the loop as | |
| \[ \sum^{\mathtt{arrSize}}_{i=1}1 = { \mathtt{arrSize} }. \] | |
But how can we relate arrSize to \( n \)? |
|
The three parameters use 32, 64, and 32 bits, respectively. The array uses 32 bits for each of the arrSize elements. |
|
| So \[ \begin{align} n & = 32 + 64 + 32 + ( 32 \times \mathtt{arrSize} ) \\ & = 128 + ( 32 \times \mathtt{arrSize} ) \end{align} \]. | |
We can then solve for arrSize to find that \[ \mathtt{arrSize} = \frac{n - 128}{32} \]. |
|
| 8 | Finally, there is no array-indexing operation on line 8. |
So we now know that \( \mathrm{C}_{\mathrm{index}}(n) = (n - 128)/32 \) is the number of array-indexing operations, where \( n \) is equal to the number of bits in the array plus the number of bits in each of the three parameters.
-
Again, we'll do that in a video, if you like.
-
If you are comfortable with the written argument, you can skip this video.
-
Yuck! I did not enjoy that!
-
You and me both!
-
It turns out that the choices we make for the quantities in our analysis can make a big difference.
-
Some quantities will be easy to work with, others less so.
-
So our choices matter! If we choose n such that it's straightforward to work with, and we pick something easy to count, we'll have an easier time with our analysis. If we make poor choices, we might make work for ourselves, or worse, have something that isn't even meaningful or useful.
(When logged in, completion status appears here.)