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

  • $\begingroup$ 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? $\endgroup$
    – greybeard
    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++) {

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.