Analyzing Algorithm Efficiency: Counting Primitive Operations

Hello! In our last lesson, we explored how an algorithm's performance can vary between best, worst, and average-case scenarios. We concluded that worst-case analysis is often the most practical measure. So far, we've been estimating complexity by looking at loop structures intuitively. Today, we're going to make that process more formal and precise.

This lesson focuses on the foundational technique that underpins all algorithm analysis: counting primitive operations. By learning to systematically count the exact number of basic computational steps an algorithm performs for an input of size n, you will gain a much deeper understanding of how we arrive at the Big-O classifications we've been discussing.

1. What is a "Primitive Operation"?

Before we can count operations, we need to define what counts as one. In algorithm analysis, we break down code into its most basic, indivisible steps, which we call primitive operations. We assume that each of these operations takes a constant amount of time to execute, regardless of the values involved.

To get a clear idea of what constitutes a primitive operation, let's look at a formal definition and some examples.

In short, a single line of C code can contain multiple primitive operations. For example, the statement x = y + z; involves:

1. One addition (+)
2. One assignment (=)

For our purposes, we'll generally count this as a fixed number of operations. The key is to have a consistent way of counting so we can compare algorithms.

2. The Frequency Count Method

The core technique for analyzing code is the frequency count method. It's straightforward:

1. Examine the code line by line.
2. For each line, determine how many primitive operations it contains.
3. Determine how many times that line is executed (its frequency).
4. The total number of operations is the sum of (operations per line) × (frequency).

Let's see this in action with a detailed walkthrough. The following video is exceptionally thorough in breaking down a simple for loop. This level of detail is exactly what's needed to build a solid foundation.

Let's consolidate the key insight for a standard for loop that iterates n times, like for (int i = 0; i < n; i++):

This n+1 detail for the condition check is a classic "gotcha" in rigorous analysis, and understanding it is a sign of mastering this topic.

The following image provides another summary of this process for a similar algorithm, which can help solidify the concept.

3. Analyzing Nested Loops

The real power of this method becomes apparent when we analyze more complex structures like nested loops. The logic remains the same, but the frequencies multiply.

If an outer loop runs n times, and for each of those iterations, an inner loop runs m times, any statement inside the inner loop will be executed a total of $n\times m$ times.

Let's watch an example that demonstrates this with matrix operations.

Let's break down the core of that matrix addition example:

// n is the dimension of the square matrix
for (int i = 0; i < n; i++) {         // Outer loop
    for (int j = 0; j < n; j++) {     // Inner loop
        c[i][j] = a[i][j] + b[i][j];  // This statement is executed n*n times
    }
}

• Outer loop header (for i): The condition i < n is checked $n+1$ times.
• Inner loop header (for j): This entire loop is part of the outer loop's body, so it runs n times. In each of those n runs, the inner loop's condition j < n is checked $n+1$ times. Total checks: $n\times (n+1)=n^2+n$.
• Innermost statement: This line is inside both loops. It runs n times (for the outer loop) × n times (for the inner loop) = $n^2$ times.

4. From Count to Cost Function

By summing the operations for each line, we can create a precise mathematical function for the total number of operations, $T(n)$.

Let's re-examine the simple array sum algorithm from the Neso Academy video, but with a typical C for loop (for i=0..n-1):

int sum_array(int arr[], int n) {
    int sum = 0;                        // c1 ops, 1 time
    for (int i = 0; i < n; i++) {       // i=0 (c2 ops, 1 time), i<n (c3 ops, n+1 times), i++ (c4 ops, n times)
        sum = sum + arr[i];             // c5 ops, n times
    }
    return sum;                         // c6 ops, 1 time
}

Let's assume each simple assignment, comparison, increment, addition, and return is 1 operation for simplicity.

• int sum = 0;: 1 operation
• int i = 0;: 1 operation
• i < n;: $n+1$ operations
• i++;: $n$ operations (let's count it as one op)
• sum = sum + arr[i];: 3 operations (array access, addition, assignment) executed n times = $3n$ operations.
• return sum;: 1 operation

Total operations $T(n)$:
$T(n)=1+1+(n+1)+n+3n+1=5n+4$

This polynomial, $5n+4$, is the cost function. From our previous lessons, you know that for large n, the dominant term is 5n, and we drop the constant factor, giving us a complexity of O(n). Counting primitive operations is the formal way we find the function that Big-O notation simplifies.

Practice Exercise

Now it's your turn. Let's analyze a code fragment where the inner loop's behavior depends on the outer loop.

Consider the following C code:

void some_function(int n) {
    long long sum = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            sum++;
        }
    }
}

Your task: Count the number of times the sum++ statement is executed. Try to write down the execution count for a few small values of n (e.g., n=1, 2, 3, 4) to spot the pattern.

Hint:

• When i = 0, the inner loop runs from j = 0 to n-1. How many times is that?
• When i = 1, the inner loop runs from j = 1 to n-1. How many times?
• ...
• When i = n-1, the inner loop runs from j = n-1 to n-1. How many times?

Conclusion

Today, you've learned the formal process that underpins algorithm analysis. Instead of just "eyeballing" loops, you can now dissect a piece of code and produce a precise mathematical function describing its performance.

Key Takeaways:

• A primitive operation is a basic computational step that takes constant time (e.g., assignment, arithmetic, comparison).
• The frequency count method involves summing the execution counts of all primitive operations in a piece of code.
• For a typical for loop running n times, the condition is checked n+1 times, while the body and increment run n times.
• Counting operations produces a cost function (e.g., $5n+4$), which we then simplify using Big-O notation to classify its complexity (e.g., $O(n)$).

Preview of the Next Lesson:
We've spent this module building up our theoretical toolkit for analyzing algorithms. It's time to put it to use! In the next lesson, we will begin our journey into fundamental algorithms by implementing and analyzing our first searching algorithm: linear search. You'll apply what you've learned about Big-O, case analysis, and operation counting to a real-world problem.