Complexity calculation

[mpg]

I have problems with this ..
For example:

i=o
while (i<n)
{
for (j=0;j<n;j++)
{...
printf ("hello");
....
}
i=i+1
}

The answer is=1 +n+1 +n*(1+n+1+n+n+1)==> 2+4*n+3*n^2
Can you explain the steps of this solution please?

[ne555]

while (i<n;j<n;j++)
¿what does that mean?

[mpg]

Excuse me... now correct my mistake..
I need help also for this:

int i=0; j=0; 
for int h=2, h<=n+1; h++) 
{
while (i<n+2) 
{cout <<i<<endl;
i++; 
}
j++, n++; n--; 
}

Thank you.

[salem c]

> h<=h+1
That's going to be true for some time....

Try to post something which
a) compiles
b) is indented correctly - or at all.

[mpg]

Today probably I have fever....

[ne555]

//n1 = n2
i = 0; //1
while (i < n1) { //the condition will execute n1+1 times
  //things inside will execute n1 times

  for (j = 0; j < n2; j++) { //same construct here
    //...
    printf("hello");
    //....
  }
  i = i + 1
}

so, outer loop
i = 0, executes 1 time
i<n1, executes n1+1 times
the inner loop executes n1 times
i = i+1, executes n1 times
that gives you
1 + n1+1 + n1*(for) + n1 = 2 + 2n1 + n2*(for)

now the inner loop
j = 0, 1 time
j<n2, n2+1 times
printf, n2 times
j++, n2 times
1 + n2+1 + n2 + n2 = 2 + 3n2

putting both together and doing n1=n2=n
2 + 2n + n (2 + 3n) = 2 + 2n + 2n + 3n^2 = 2 + 4n + 3n^2


however, keep in mind that printf() does not take the same time than i<n

[mpg]

Many thanks ne555.
Can you help me also for this ?

int i=0; j=0;
for int h=2, h<=n+1; h++) 
{
while (i<n+2) 
{cout <<i<<endl;
i++;
}
j++, n++; n--; 
}

[salem c]

> for int h=2, h<=h+1; h++)
Still got a fever huh?

60+ posts, you ought to have figured out how to indent code.

> n++; n--;
Fo sure, n will not change.

And both loops are O(N²).
https://en.wikipedia.org/wiki/Big_O_notation
Because as N tends to infinity, the only term which matters is the one with the highest power.

[mpg]

Correct now.
I don' t understand all well I live in Italy and probably some explanations are different in your country..
For example read here.
The final assigment 1 in the "while" loop, but in the explanation of ne555 there isn't in this kind so I have difficulty to understand this difference
https://www.dropbox.com/s/xlegr4xytdp6f2c/complessita2.jpg?dl=0

[jonnin]

Formal big-O for a piece of code will be almost exactly the same everywhere. But like math proofs, formal big-o is too much to go into most of the time, so you have some different words from different people when we swap to natural language to describe it.

We are all saying the same things.

[Enoizat]

The final assigment 1 in the "while" loop, but in the explanation of ne555 there isn't in this kind so I have difficulty to understand this difference

Please, next time do not post a link to an image, but type the text: you are the one who is expected to do the hard work, if you want good answers.

- - -
Original text:

Esempio 4 - Cicli annidati:

i = 0;
while ( 1 < n ) {               // n+1 test
    for ( j = 0; j < n; j++ ) { // un ciclo for per ogni while
        printf("CIAO!");        // una scrittura per ogni for
    }
    i = i + 1;                  // un assegnamento per ogni while
}

Assegnamento esterno:        1+
Test while:                  n+1+
Cicli while:                 n*(
Assegnamento iniziale for:   1+
Controlli ciclo for:         n+1+
Incrementi ciclo for:        n+
Scritture:                   n+
Assegnamento:                1
- - -
Numero totale di passi base: 2+4*n+3*n2

- - -


- - -
Translated by Google Translator
Example 4 - Nested cycles:

i = 0;
while (1 <n) {                  // n + 1 test
    for (j = 0; j <n; j ++) {   // one for loop for each while
        printf ("HELLO!");      // one script for each for
    }
    i = i + 1;                  // an assignment for each while
}

External assignment:         1+
Test while:                  n + 1 +
While loops:                 n * (      <-- please notice there’s a parenthesis here
Initial assignment for:      1+
For loop controls:           n + 1 +
Increments for loop:         n +
Scriptures:                  n +
Assignment:                  1          <-- a closing parenthesis is missing here
- - -
Total number of basic steps: 2 + 4 * n + 3 * n2

Writing the above numbers in a row (instead of a column), it becomes:
1 + n + 1 + n*(1 + n + 1 + n + n + 1)

Let’s carry out the multiplication:
1 + 1 + n + n + n2 + n + n2 + n2 + n

Let’s tidy up:
1 + 1 + n + n + n + n + n2 + n2 + n2

Let’s perform the additions:
2 + 4*n + 3*n2

That’s exactly how ne555 describes it.

[Enoizat]

Indeed there’s a discrepancy, now I can see it.
In the image you provided us, the last line says: “Assignment: 1”.
That ‘assignment’ (the only one left) must be

i = i + 1;

That’s *not* included in the for loop, so the parentheses should close the line before and the last line should be “Assignment: n”.

You’re right, there’s an error in your text, which by chance is ‘solved’ by the multiplication.

[mpg]

You means that the error is here?

External assignment: 1+
Test while: n + 1 +
While loops: n * ( <-- please notice there’s a parenthesis here
Initial assignment for: 1+
For loop controls: n + 1 +
Increments for loop: n +
Scriptures: n + ) <-- a closing parenthesis is missing here
Assignment: 1 ERRROR i=i+1 ---->n




******

Can you help also for this please?

int i=0; j=0; 
for int h=2, h<=n+1; h++) 
{
while (i<n+2) 
{cout <<i<<endl;
i++; 
}
j++, n++; n--; 
}

[Enoizat]

There are several syntax errors in your last code.
Are you sure you’ve copied it correctly?

And where do these question come from? It seems you need to pass a test or an exam. We can’t do that for you.

Anyway, this is my guess, but I don’t guarantee it’s correct:

int i {};                           // 1
int j {};                           // + 1
for ( int h { 2 };                  // + 1
      h <= n + 1;                   // + (n + 1) * [
      /**/ )
{
    while ( i < n + 2 )             // + (n + 3) * (
    {
        std::cout << i << '\n';     // + 1
        ++i;                        // + 1 )
    }
    ++j;                            // + 1
    ++n;                            // + 1
    --n;                            // + 1
    ++h;                            // + 1 ]
}

1 + 1 + 1 + (n + 1) * [(n + 3) * (1 + 1) + 1 + 1 + 1 + 1]
                                   \ /
                                    2

3 + (n + 1) * (2*n + 6 + 4)

(n + 1) * (2*n + 10) + 3

2*n2 + 10*n + 2*n + 10 + 3

2*n2 + 12*n + 13

[mpg]

Many thanks!!
It isn't a test fo an exam!!
It is only an exercise that I wish to do at home , but really I have some problems, with you I search to understand well the argument.
You say " I don’t guarantee it’s correct:"" where are your doubts?

[Enoizat]

where are your doubts?

My level at math ;-)

[mpg]

For this?

i=1                         //1
while(i<n*n+1)      // n^2+1??
{
i++                      //n^2??
}

Total= 2n^2+2???