Unit 2.12: Informal Run-Time Analysis

Statement Execution Count

An informal way to analyze the efficiency of code is to count the number of times a key statement is executed.

This statement execution count can often be determined by tracing the execution of its loops.

Single Loop Analysis

In a simple loop, a statement inside the loop is executed as many times as the loop iterates.

Task: Analyzing the execution count of a single loop.

public class SingleLoopAnalysis {
    public static void main(String[] args) {
        int count = 0;
        int n = 5;
        for (int i = 0; i < n; i++) {
            // This statement is executed n times
            count++; 
        }
        System.out.println("Execution count: " + count); // Prints 5
    }
}

Nested Loop Analysis

For nested loops, a statement inside the inner loop is executed (outer loop iterations) $\times$ (inner loop iterations) times.

Task: Analyzing the execution count of nested loops.

public class NestedLoopAnalysis {
    public static void main(String[] args) {
        int count = 0;
        int n = 5;
        int m = 4;

        // The outer loop runs n times
        for (int i = 0; i < n; i++) {
            // The inner loop runs m times for each outer loop iteration
            for (int j = 0; j < m; j++) {
                // This statement is executed n * m = 20 times
                count++;
            }
        }
        System.out.println("Execution count: " + count); // Prints 20
    }
}

Comparing Efficiencies

By counting executions, we can compare two different algorithms to see which is more efficient. Statement execution counts are often calculated informally through tracing and analysis of iterative statements. For example, a single loop that runs $n$ times is generally more efficient than nested loops that run $n^2$ times as the value of $n$ grows.