When writing algorithms, one of the most important skills you can develop is the ability to evaluate how efficient your code is. This is where Big O Notation comes into play. This guide’ll explain how to calculate Big O complexity specifically for Java programs involving loops, nested loops, and loops with uncommon increments like +2, /2, etc. Even though examples are written in Java, the technique is the same for all programming languages.

What is Big O Notation?

Big O Notation describes how the runtime of an algorithm scales with input size n. It helps in measuring the complexity and efficiency of the algorithm generically. It helps us focus on the growth rate rather than exact runtimes, which makes it essential for analyzing performance. 

1. Single Loops

The complexity of a basic loop is directly proportional to how many times it runs.

Example: Single Loop, increment by 1

for (int i = 0; i < n; i++) {
    System.out.println(i);
}

• Number of iterations: n
• Time complexity: O(n)

Example: Increment by 2

for (int i = 0; i < n; i += 2) {
    System.out.println(i);
}Code language: HTML, XML (xml)

• Executes about n/2 times.
• Constants are dropped in Big O → Still O(n)

2. Nested Loops

When you have loops inside other loops, you multiply their complexities.

Example: Classic Nested Loop

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        System.out.println(i + ", " + j);
    }
}Code language: JavaScript (javascript)

• Outer loop: n times
• Inner loop: n times
• Total time: n * n = O(n²)

Example: Varying Inner Loop

for (int i = 0; i < n; i++) {
    for (int j = 0; j < i; j++) {
        System.out.println(i + ", " + j);
    }
}Code language: JavaScript (javascript)

• The inner loop runs 1 + 2 + 3 + … + (n-1) = n(n-1)/2 times
• Time complexity: O(n²)

Step-by-Step Analysis:

• The outer loop runs from i = 0 to i < n → n iterations.
• The inner loop runs from j = 0 to j < i → i iterations per outer iteration.

Let’s compute the total number of iterations (i.e., how many times the inner loop body executes)

When i = 0 → j runs 0 times  
When i = 1 → j runs 1 time  
When i = 2 → j runs 2 times  
...  
When i = n-1 → j runs n-1 times

So the total iterations over all values of i is:

0 + 1 + 2 + 3 + ... + (n - 1) = n(n - 1)/2

3. Consecutive Loops

Sequential loops add their complexities (but only the dominant one matters).

for (int i = 0; i < n; i++) {
    System.out.println("First loop: " + i);
}

for (int j = 0; j < n; j++) {
    System.out.println("Second loop: " + j);
}Code language: JavaScript (javascript)

• Both loops are O(n)
• Combined: O(n) + O(n) → Still O(n)

4. Loops with Non-Linear Increments

These are loops where the counter changes multiplicatively or by another pattern.

Tip: Whenever you see divide or multiply by a number ( i/2 or i*2 ), it is mostly log times

Example: Divide by 2

int i = n;
while (i > 1) {
    i = i / 2;
    System.out.println(i);
}Code language: JavaScript (javascript)

• n, n/2, n/4, …, until 1 → Total ≈ log₂(n)
• Time complexity: O(log n)

Example: Multiply by 2

int i = 1;
while (i < n) {
    System.out.println(i);
    i = i * 2;
}Code language: HTML, XML (xml)

• i = 1, 2, 4, 8, …, up to n → Again log₂(n) steps
• Time complexity: O(log n)

If we multiply or divide by 3 instead of 2, the complexity will be log₃(n).

Summary