Algorithms for Coding Interviews in Java/

...

/

Example: Measuring Time Complexity of a Single Loop Algorithm

Example: Measuring Time Complexity of a Single Loop Algorithm

In this lesson, you will learn how to compute the time complexity of an algorithm that involves a for loop.

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::

Press + to interact
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 ...

Access this course and 1400+ top-rated courses and projects.