Easy way to calculate time complexity

Using the example below for illustration

void f(int n)
{
    int i;
    int j;

    for (i = 0; i < n; i++)
    {
        if (i % 2 == 0)
        {
            for (j = 1; j < n; j = j * 2)
            {
                printf("[%d] [%d]\n", i, j);
            }
        }
        else
        {
            for (j = 0; j < n; j = j + 2)
            {
                printf("[%d] [%d]\n", i, j);
            }
        }
    }
}

Step 1: Identify the loops

• We have two nested loops in the function: an outer loop and an inner loop.

Step 2: Determine the number of iterations in each loop

• Outer loop: The outer loop runs from i = 0 to i = n-1, so it has n iterations.

• Inner loop (when i is even): The inner loop starts from j = 1 and doubles j in each iteration until it reaches n. The values of j in this loop are 1, 2, 4, 8, ..., up to n-1, or the largest power of 2 that is less than n. The number of iterations in this loop can be approximated as log2(n).

• Inner loop (when i is odd): The inner loop starts from j = 0 and increments j by 2 in each iteration until it reaches n-1. The values of j in this loop are 0, 2, 4, 6, ..., up to n-2, or half of the values in the range 0 to n-1. The number of iterations in this loop can be approximated as n/2.

Step 3: Compute the total number of iterations

• Since the inner loop's behavior depends on the value of i (even or odd), we need to consider both cases:

  • When i is even, the number of iterations in the inner loop is approximately log2(n).

  • When i is odd, the number of iterations in the inner loop is approximately n/2.

• The total number of iterations can be computed by adding the number of iterations in the inner loop (even case) and the number of iterations in the inner loop (odd case) for each value of i.

Step 4: Compute the time complexity

• Based on the total number of iterations, we can determine the time complexity. Generally, we look at the dominant term in the number of iterations.

• The time complexity of the function will be the dominant term.

Now, let's put it all together:

• The outer loop has n iterations (O(n)).

• The number of iterations in the inner loop when i is even is approximately log2(n) (O(log n)).

• The number of iterations in the inner loop when i is odd is approximately n/2 (O(n)).

Now, let's see how these inner loops contribute to the overall time complexity:

1. When i is even, the time complexity of the inner loop is O(log n) since it runs log2(n) times.

2. When i is odd, the time complexity of the inner loop is O(n) since it runs n/2 times.

When analyzing time complexity, we focus on the most significant term that dominates the overall growth rate. In this case, O(n) is more significant than O(log n). So, when combining both cases (even and odd values of i), the overall time complexity of the function is O(n) * O(n) = O(n^2).

The presence of the O(n) term from the inner loop with odd i values makes the overall time complexity of the function O(n^2).

Using the example below to touch all the time complexity functions available

void complexFunction(int n) {
    int i, j, k;

    // O(1) operation
    printf("O(1) operation\n");

    // O(n) loop
    for (i = 0; i < n; i++) {
        // O(1) operation
        printf("[%d] O(1) operation\n", i);
    }

    // O(n^2) nested loop
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            // O(1) operation
            printf("[%d][%d] O(1) operation\n", i, j);
        }
    }

    // O(n^3) nested loop
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            for (k = 0; k < n; k++) {
                // O(1) operation
                printf("[%d][%d][%d] O(1) operation\n", i, j, k);
            }
        }
    }

    // O(log n) loop
    for (i = 1; i < n; i *= 2) {
        // O(1) operation
        printf("[%d] O(1) operation\n", i);
    }

    // O(n log n) nested loop
    for (i = 1; i < n; i++) {
        for (j = 1; j < n; j *= 2) {
            // O(1) operation
            printf("[%d][%d] O(1) operation\n", i, j);
        }
    }
}

Explanation:

1. The function starts with an O(1) operation (constant time complexity).

2. The first loop runs n times, giving it a time complexity of O(n).

3. The second nested loop runs n^2 times, resulting in a time complexity of O(n^2).

4. The third nested loop runs n^3 times, leading to a time complexity of O(n^3).

5. The fourth loop runs log n times, making it O(log n).

6. The fifth nested loop runs n * log n times, giving it a time complexity of O(n log n).

The Final Time Complexity(of all the time complexity functions)

To determine the overall time complexity of the function, we need to consider the time complexities of all the loops present in the function and find the dominant term.

Let's break down the time complexities of each part:

1. O(1) operation: This has constant time complexity and doesn't depend on the value of n. It doesn't affect the overall time complexity.

2. O(n) loop: This loop runs n times, contributing O(n) to the overall time complexity.

3. O(n^2) nested loop: This nested loop runs n^2 times, contributing O(n^2) to the overall time complexity.

4. O(n^3) nested loop: This nested loop runs n^3 times, contributing O(n^3) to the overall time complexity.

5. O(log n) loop: This loop runs log n times, contributing O(log n) to the overall time complexity.

6. O(n log n) nested loop: This nested loop runs n * log n times, contributing O(n log n) to the overall time complexity.

Now, let's compare the complexities:

O(n) < O(n log n) < O(n^2) < O(n^3)

The most significant term that dominates the overall time complexity is O(n^3) since it grows faster than all the other terms. Therefore, the overall time complexity of the function is O(n^3)