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

Line(s)
1–2	There are no increments on these lines.
3–7	Here we have a loop, which is run \( n \) times.
	In each iteration of the loop, we definitely perform one increment on the loop variable.
	In the best case, x is smaller than all elements in the array. In that case, we never perform the increment on line 5.
	So we can characterize the number of increments in the loop as \( \sum^{n}_{i=1} 1 = n \).
8	There are no increments on line 8.

All told, that gives us the best-case number of increments as \( \mathrm{C}_{\mathrm{best-inc}}( n ) = n \), where \( n \) is the size of the array.

Here's a video to walk you through the analysis:

Worst-Case Analysis

Let's let

• \( n \) be the number of elements in the array and
• \( \mathrm{C}_{\mathrm{worst-inc}}(n) \) be the largest number of increment operations the algorithm will perform for an array of size \( n \).

Looking at our code, we can see

Line(s)
1–2	No increments on these lines.
3–7	A loop that runs \( n \) times.
	In each iteration of the loop, we definitely perform one increment on the loop variable.
	In the worst case, x is larger than all elements in the array. In that case, we always perform the increment on line 5.
	So we can characterize the number of increments in the loop as \( \sum^{n}_{i=1} 2 = 2n \).
8	There are no increments on line 8.

That analysis gives us the worst-case number of increments as \( \mathrm{C}_{\mathrm{worst-inc}}(n) = 2n \), where \( n \) is the size of the array.

A video to walk through the analysis:

Conclusion

From our analysis, here are some statements we can safely make, where \( n \) is the size of the array:

• In the best case, the algorithm performs \( n \) increments.
• In the worst case, the algorithm performs \( 2n \) increments.

And from this information we can say the following about the algorithm as a whole:

• It performs at least \( n \) increments.
• It performs no more than \( 2n \) increments.