Search⌘ K
AI Features
Home
Courses
Algorithms for Coding Interviews in Java

Example: Measuring Time Complexity of a Single Loop Algorithm

Understand how to measure the time complexity of a single loop algorithm in Java by counting primitive operations. Learn to evaluate each part of the loop, including initialization, increments, and comparisons, to derive the total runtime formula for effective asymptotic analysis.

We'll cover the following...

A for loop with n iterations

Now, let’s consider what happens when a loop is involved. Consider the following Java program::

Java
class Sum {
  public static void main(String args[]) {
    int n = 10; // 1 step
    int sum = 0; // 1 step
    for (int i = 0; i < n; i++) {
      sum += 1; // n steps
    }
    System.out.println(sum); // 1 step
    
  }
}

Let’s count the number of primitive operations in the above program. First, look at lines 4 and 5 where variable initializations are taking place. These account for one primitive operation, each.

Line 6 is a loop statement. To count the number of primitive operations on that line, we must dissect it into its constituents: the initialization, the increment, and the test. The initialization occurs only once and is counted as one primitive operation. The increment (i++i++) operation must read the current value of variable ii, add 11 to it, and store the result back in variable ii. That’s three primitive operations. The test operation (i<ni < n) must read ...