# Big-O Notation: Runtime Analysis

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)

Kind Regards

• Welcome to ComputerScience@SE. Please edit your question to contain all information needed to answer it - hyperlinks welcome for details & reference. See How do I ask a Good Question? Feb 2 '20 at 7:56

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.

• thank you for the fast reply, so just that i get that right in this case m is n+1?
– Beni
Feb 2 '20 at 7:06