How to figure out time complexity of complex programs

Question

For example:

#include <iostream>
using namespace std;

int main() {
    int n, s = 0, i, j, k;

    cin >> n;

    for (i = 1; i <= n * n; i++) {
        for (j = 1; j <= i / 2; j++) {
            s += i + j;
        }

        k = 1;
        while (k < j) {
            s += k;
            k += 2;
        }
    }

    cout << s << endl;
    return 0;
}

How do I approach this?

• The outer loop runs from 1 to n^2
• The inner loop runs from 1 to i/2
• The while loop runs while k is less than j

So, the time complexity should be larger than O(n^2), but this is where I get stuck. Any help would be appreciated

Answer 1

Let's compare the first and second inner loops. The code in their bodies represents O(1) time complexity (assuming arithmetic operations have constant time). After the first inner loop has completed, j is equal to i/2+1. As the second loop has k increasing with steps of 2, it will make half the number of iterations of what the first loop did. That means in terms of asymptotic behaviour they represent the same time complexity (a coefficient is not significant), and so we can ignore the second inner loop.

The first inner loop has this number of iterations:

      0 + 1 + 1 + 2 + 2 + 3 + 3 + ... + (𝑛²−1)/2 + 𝑛²/2

If 𝑛 is odd, this is the same as:

      2(0 + 1 + 2 + ... + 𝑛²/2)

If 𝑛 is even, the final term 𝑛²/2 is not equal to its predecessor (𝑛²−1)/2, so its value only occurs once, not twice like the other values:

      2(0 + 1 + 2 + ... + 𝑛²/2) − (𝑛²/2)

The sum in parentheses, i.e. (0 + 1 + 2 + ... + 𝑛²/2), is a triangular number:

      (𝑛²/2)(𝑛²/2+1)/2

When multiplied by 2, the division can be left out. For odd 𝑛 (and thus odd 𝑛²) we get:

      (𝑛²/2)(𝑛²/2+1) = 𝑛⁴/4 + 𝑛²/2

For even 𝑛 we get:

      𝑛⁴/4

In either case the complexity is thus O(𝑛⁴)