Java · Course navigation

Java: counting operations to see growth rates

Count loop iterations instead of timing them to compare linear, quadratic, and logarithmic growth.

On this page

Before you start

Java loops and arrays.

Count loop iterations instead of timing them to compare linear, quadratic, and logarithmic growth.
Predict the sample output and explain the state changes.
Complete the practice task and check the boundary cases.

The concept

Analysis of algorithms asks how the work grows as the input size n grows. Timing a program mixes in the machine, the JVM warm-up, and the garbage collector, so a clean way to see growth is to count the basic steps directly.

A single loop over n items does about n steps, two nested loops over n items do about n squared steps, and a loop that halves its counter does about log2(n) steps. Doubling n doubles the first, quadruples the second, and adds only one step to the third.

Code example

Java

class Main {
  static long[] count(int n) {
    long linear = 0, quadratic = 0, logarithmic = 0;
    for (int i = 0; i < n; i++) {
      linear++;
    }
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        quadratic++;
      }
    }
    for (int k = n; k > 1; k /= 2) {
      logarithmic++;
    }
    return new long[] {linear, quadratic, logarithmic};
  }

  public static void main(String[] args) {
    for (int n : new int[] {8, 16, 32}) {
      long[] c = count(n);
      System.out.println("n=" + n + " linear=" + c[0] + " quadratic=" + c[1] + " log=" + c[2]);
    }
  }
}

Output

n=8 linear=8 quadratic=64 log=3
n=16 linear=16 quadratic=256 log=4
n=32 linear=32 quadratic=1024 log=5

Example details

Follow the code

Open the walkthrough to inspect the example one step at a time.

Show guided walkthrough

Guided walkthroughReady

1class Main {

2 static long[] count(int n) {

3 long linear = 0, quadratic = 0, logarithmic = 0;

4 for (int i = 0; i < n; i++) {

5 linear++;

6 }

7 for (int i = 0; i < n; i++) {

8 for (int j = 0; j < n; j++) {

9 quadratic++;

10 }

11 }

12 for (int k = n; k > 1; k /= 2) {

13 logarithmic++;

14 }

15 return new long[] {linear, quadratic, logarithmic};

16 }

18 public static void main(String[] args) {

19 for (int n : new int[] {8, 16, 32}) {

20 long[] c = count(n);

21 System.out.println("n=" + n + " linear=" + c[0] + " quadratic=" + c[1] + " log=" + c[2]);

22 }

23 }

24}

Follow the example

Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.

View the complete dry-run table

Prepared trace of the published program. Some rows group repeated iterations.
What happens	State after step	Output so far
The first loop adds one for each of the n iterations.	`n = 8, linear = 8`	—
The inner statement runs n times for each of the n outer passes.	`n = 8, quadratic = 64`	—
k goes 8, 4, 2, then stops at 1, so there are three halvings.	`k = 8 → 4 → 2 → 1, log = 3`	—
Print one row per size. Each time n doubles, linear doubles, quadratic quadruples, and log grows by one.	`k = 8 → 4 → 2 → 1, log = 3`	n=8 linear=8 quadratic=64 log=3 n=16 linear=16 quadratic=256 log=4 n=32 linear=32 quadratic=1024 log=5

Behind the scenes

How Java processes this code

The Java compiler produces bytecode. The JVM loads the class and invokes its main method.

Cost and common mistakes

The three loops take Θ(n), Θ(n²), and Θ(log n) time with O(1) extra space.

Counting steps measures growth, not seconds. Constant factors, caching, and the JIT compiler still affect real running time.
An int counter would overflow for large quadratic counts; the example uses long.

Try it yourself

Predict the three counts for n = 64.

Reveal answer and reasoning

linear = 64, quadratic = 4096, and log = 6, because 64 halves six times to reach 1.