Time complexity and big-O of double loop algorithm

Question

I am playing around with calculating the time complexity of the following code:

    for (int i = 0; i <= n/2; i+=3){
        for (int j = i; j <= n/4; j+=2) {
            x++;
        }
    }

I know that its big-O complexity is N^2. However, I try to extract some formula that I could deduce that based on that formula. What I have done so far.

I know since the inner loop terminates at n/4 we can actually rewrite this code to:

for (int i = 0; i <= n/4; i+=3){
    for (int j = i; j <= n/4; j+=2) {
        x++;
    }
}

If we relax a bit we can say that this double loop will be approximately the same as :

for (int i = 0; i < n/4; i+=3){
    for (int j = i; j < n/4; j+=2) {
        x++;
    }
}

just to facilitate the math. I am stuck at this point, I think we can rewrite that as :

$$\sum_{k=0}^{n/12} n/8 - 3i/2 $$ but I am not sure if it makes any sense.

Answer 1

The inner loop runs $n/8-i/2$ times, give or take a $O(1)$ correction due to the parity of $n/4-i$, provided $i\le n/4$, which happens for $n/12+O(1)$ values of $i$. Therefore, $x$ increments a number of times $\sim$-equivalent to$$\tfrac{n^2}{96}-\sum_{k=1}^{n/12}(3k)/2\sim\tfrac{n^2}{96}-\tfrac34(\tfrac{n}{12})^2=\tfrac{n^2}{192},$$where $f\sim g$ iff $f-g\in o(n^2)$.