Big-O Notation: Runtime Analysis

Question

I have a problem with an exercise, I have to analyze the following For-Loops

Then I have to write down the explicit notation, my problem is that I don't know how to get the right m. I tried this but now I have no idea how to get the m, because I thought that m defines the diffrence between i and j and so I became m = n + 2 but that was wrong. (This is the form in which it has to be)

I would really appreciate your help thx for your efforts in advance.

Kind Regards

Answer 1

Just for convenience, I'll write out the code first.

for(int i = 0; i <= 4 * n;  i = i + 4) {
    for(int j = 0; j <= i + 1; j++) {
        meth(); 
    }
}

and meth() runs in constant time $O(1)$.

Right away we can use that the outer loop runs $n+1$ times (assuming $n$ is a non-negative integer) since we are doing $0$ to $4n$ inclusive in increments of 4. The inner loop runs $i+2$ times for each iteration of the outer loop since it goes from 0 to $i+1$ inclusive in increments of 1. So we can write the total number of times the inner loop runs as

$$\sum_{i=0}^{n} (4i+2) = \sum_{i=0}^n4i + \sum_{i=0}^n2 = 4\sum_{i=0}^ni + 2(n+1) = 4\frac{n(n+1)}{2}+2(n+1) = 2(n+1)^2$$

In the arithmetic, we first break up the sum into two parts. Then we factor out the 4 in the first term and use that that we added 2 $(n+1)$ times, aka 2(n+1). Next, we use the formula $\sum_{i=0}^n i = \frac{n(n+1)}{2}$ and then finally simplify.