Informal Run-Time Analysis

Hello! I'm Saavi, and I'm so glad you're here. Today, we're tackling a topic that forms the foundation of writing not just correct code, but good code.

What's a "Statement Execution"?

First, let's get our terms straight. A statement is just a single action in your code. Think of it like one instruction in a recipe.

System.out.println("Go, Huskies!");

That's one statement. When your program runs this line, we call that one statement execution.

A statement execution count is simply the total number of times a statement is run during a program. If that line were inside a loop that ran 10 times, its execution count would be 10.

Why Bother Counting?

Think back to the sandwich example. Your method (the assembly line) and Carlos's method (running back and forth) both get the job done. But if you were running a sandwich shop like Subway, you'd want the most efficient process to serve customers quickly.

In programming, efficiency matters. An efficient app on your phone uses less battery. An efficient search on a website like Amazon gives you results in a split second, not a full minute. By counting statement executions, we get a simple way to measure and compare this efficiency.

Counting Executions in a Single Loop

Let's start with the most common structure: a for loop.

int n = 10;
for (int i = 0; i < n; i++) {
  System.out.println("Processing item..."); // This is the statement we'll count
}

How many times will "Processing item..." be printed?

Let's trace it:

• i starts at 0. 0 < 10 is true. Print. (1st time)
• i becomes 1. 1 < 10 is true. Print. (2nd time)
• ...
• i becomes 9. 9 < 10 is true. Print. (10th time)
• i becomes 10. 10 < 10 is false. The loop stops.

The statement inside the loop executed 10 times. In general, for a loop that goes from 0 to n-1, the body executes n times. This is a fundamental pattern you should recognize immediately.

The Game Changer: Nested Loops

This is where things get interesting, and where code can suddenly become much less efficient. A nested loop is a loop inside another loop.

Imagine we're creating a coordinate grid for a simple game, printing the coordinates for every point.

int rows = 4;
int cols = 5;

for (int i = 0; i < rows; i++) {       // Outer loop
  for (int j = 0; j < cols; j++) {     // Inner loop
    System.out.println(i + ", " + j);  // The statement we're counting
  }
}

How many times does the println statement run?

Think about it:

• The outer loop runs for i = 0.
• Inside that single run, the inner loop runs completely. It runs for j = 0, 1, 2, 3, 4. That's 5 times.
• Then the outer loop runs for i = 1.
• The inner loop runs again, completely. j = 0, 1, 2, 3, 4. That's another 5 times.
• This repeats for i = 2 and i = 3.

So, for each of the 4 runs of the outer loop, the inner loop's statement executes 5 times.

The total count is *`rows cols**, which is4 * 5 = 20` times.

Analogy Time: Think of it like a calendar. The outer loop is the week (7 days). The inner loop is the hours in a day (24 hours). To find the total hours in a week, you don't add 7 + 24. You multiply 7 * 24. It's the same principle.

Informal Comparison

Now we can use these counts to make decisions. Let's say we have two algorithms to process some data of size n.

Algorithm A:

for (int i = 0; i < n; i++) {
  // do one thing
}

Statement execution count: n

Algorithm B:

for (int i = 0; i < n; i++) {
  for (int j = 0; j < n; j++) {
    // do one thing
  }
}

Statement execution count: *`n n**, or **n^2`**

If n is 10:

• Algorithm A runs its statement 10 times.
• Algorithm B runs its statement 100 times.

If n is 1,000:

• Algorithm A runs its statement 1,000 times.
• Algorithm B runs its statement 1,000,000 times!

You can see that Algorithm B gets slow very quickly as n increases. Even though both might be "correct," Algorithm A is far more efficient. This is an informal run-time comparison. We're not using a stopwatch; we're using logic and simple math to predict performance. This is a critical skill for any programmer.

Let's walk through a few examples together. The key is to go slow and trace the code, just like the computer would.

Example 1: A Simple for Loop

Problem: Your classmate, Priya, wrote some code to print a list of welcome messages. How many times does the statement System.out.println("Welcome!"); execute?

public void printWelcomes(int num) {
  for (int i = 1; i <= num; i++) {
    System.out.println("Welcome!");
  }
}

// Somewhere else in the code, it's called like this:
printWelcomes(5);

Step-by-step Solution:

1. 1
   Identify the loop and the target statement

   The loop is for (int i = 1; i <= num; i++). The target statement is System.out.println("Welcome!");.
2. 2
   Determine the value of the control variable

   The method is called with printWelcomes(5), so num is 5. The loop condition is effectively i <= 5.
3. 3
   Trace the loop's execution

   • i starts at 1. 1 <= 5 is true. println executes. (Count: 1)
   • i becomes 2. 2 <= 5 is true. println executes. (Count: 2)
   • i becomes 3. 3 <= 5 is true. println executes. (Count: 3)
   • i becomes 4. 4 <= 5 is true. println executes. (Count: 4)
   • i becomes 5. 5 <= 5 is true. println executes. (Count: 5)
   • i becomes 6. 6 <= 5 is false. The loop terminates.
4. 4
   State the final count

   The println statement executes exactly 5 times.

public void findPairs(int[] arr) {
  for (int i = 0; i < arr.length; i++) {
    for (int j = 0; j < arr.length; j++) {
      if (arr[i] == arr[j]) { // How many times does this check run?
        // ... do something
      }
    }
  }
}

// Called with an array of length 5.
int[] myNums = {10, 20, 30, 40, 50};
findPairs(myNums);

Ready to try a couple on your own? Don't worry about writing the full code, just focus on the counting.

1. 1
   Heating Up

   A microwave's timer code is supposed to beep() every second. How many times will beep() be called by this code snippet?

   int start = 60; // seconds
   int end = 0;
   
   for (int i = start; i > end; i--) {
     beep();
   }

   Hint: This loop counts down. Does that change how many times it runs? Trace the first and last values of i that make the condition i > end true.

2. 2
   Team Matchups

   A basketball league in Dallas needs to schedule games. The code below iterates through a list of teams. How many times is scheduleGame() called, in terms of numTeams?

   int numTeams = 10; // Let's say there are 10 teams
   for (int team1 = 0; team1 < numTeams; team1++) {
     for (int team2 = team1 + 1; team2 < numTeams; team2++) {
       scheduleGame(team1, team2);
     }
   }

   Hint: This is tricky! The inner loop doesn't always start at 0. Try tracing it with a small numTeams like 4. Write down the pairs of (team1, team2) that get scheduled. Can you see a pattern? This is a very common and important algorithm pattern!