Some exercise about complexity

Excuse can you tell me about these exercises that I have done, are they all correct?
Many thanks!!

1
2
3
4
5
6
7
8
9
10
11
12
13
i=2;                              //   +1
j=0;                              // +1

for (i=1; i<n; i++)                //(n-1)   1  +n   +1
{
        while (j<n)               // n+1
       {
           cout <<a;              //n
           j++;                  // n
        }
}

//1+1+1  +n     +(n-1)*(n+1+  n+   n+   1) =3n^2+1   


1
2
3
4
5
6
7
8
9
10
11
12
j=1;                           //  1
for (i=1; i<n; i++)            //n-1   1  + n   +1
{
        while (j<n)            // n
       {
           cout <<a;            //n-1
           j++;                 // n-1
        }
}


//1+1+  n+    +(n-1)*(n+   n-1+   n-1+   1)   =5n-2 


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
i=1;                               //    1
b=9;				   //  1

while (i<n)		           //n	
{
        for (int  j=1; j<m; j++)   //(n-1)   1 + m  +(m-1)
       {
           cout <<a;		  //	m-1
           cout<<b;		  //	m-1
        }
i++;				 // 1 
}

//1+1+n +  (n-1)* (1  + m  +m-1   +m-1    +m-1 +1)=4mn-4m+3


1
2
3
4
5
6
7
8
9
10
11
12
i=1;                               //            1
b=0:				   //       1	
while(i<n)			  //     n
{
     for (int j=0;  j<m;  j++)      //      (n-1)   1    +m+1    + m
     cout<<a;                       //      m

cout<<b;                             //    1
i++;                                 //      1
}

//1+1+n+  (n-1)*(1+    m+1+     m+  m+   1+  1)= 3n^3-n^2 
Last edited on
1
2
3
4
5
6
7
8
9
for (i=1; i<n; i++)          //for all n  
{
        while (j<n)              //this only happens one time.  n is 100.  this goes 99 times. but now
       {                             //j is 99.  n and j do not change in these loops (apart from the j++). 
                                      //so after the first time
           cout <<a;            //the inner while loop is skipped very time.  right?
           j++;                   
        }
}


so the answer is that the inner loop happens once, and the outer loop just burns N increments.
its O(n) for that one inner loop execution, due to j starting at 0. Its the same as if the outer loop did not exist.

I only looked at the first one, on the grounds that you probably make similar mistakes on the others. you have to look at what actually happens in the loops, not just blindly count.
Last edited on
In the first exercise i=1 so the count of the for is n-1 until it will out of th cycle why n????
In while (j<n) we must remember that J=0 so the count of th while is n+1 why not?
I don't undertand .....
Last edited on
n, n-1, complexity ignores constants. Exactly counting isnt done, its ballpark, no one cares if a loop executes 100 vs 99 times, its still 'about n times'.

Look at it.
first outer loop iteration:
i = 1
j = 0 //assuming caps is typo?
n is 100.
while j < 100
{
j++
}

the while loop executes 100 times approximately, or N times.

outer loop 2:
j has not been changed anywhere, j is 100.
while 100 < 100 //does not happen.
outer loop 3:
while 100 < 100 // again, does not happen...

if the outer for loop reset j to zero every time, it would be very different, but it does not do this. the outer loop does nothing N-1 times and does N work 1 time. 1*n = n. You do about N cout statements, the O of this is O(n). This shows that the outer loop is not needed and is bloating the code and should be removed from the algorithm: your code is not well written for what it is doing. So practical analysis shows you that this block needs a re-write.

or are you trying to count something else, and not normal complexity analysis? If you want to count the # of times something happens, like the condition of the while loop, that happens about N times the first go and then another N times (once per loop) for the outer loop, about 2*n times give or take a couple (you can figure out the exact count yourself).
Last edited on
I need to count the complexity of code fragment in basic number of steps.
For example
1
2
3
4
5
6
7
i = 0;
while (1 <n) {                  
    for (j = 0; j <n; j ++) { 
        printf ("HELLO!");     
    }
    i = i + 1;  
}

is

1
2
3
4
5
6
7
8
9
10
11
External assignment:         1+
Test while:                  n + 1 +
While loops:                 n * (    
Initial assignment for:      1+
For loop controls:           n + 1 +
Increments for loop:         n +
Scriptures:                  n +
Assignment:                  1)       
- - -
Total number of basic steps: 2 + 4 * n + 3 * n^2


I am sure that this exercise is right.
Last edited on
Ok. If you think you have it right, I will leave you with this, which prints 100 when it exits.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<iostream> 
int main()
{
	
 int i; 
 int j = 0;
 int n = 100;
 int ct = 0;
  
for (i=1; i<n; i++)              
{
        while (j<n)              
       {
           //cout <<a;             
		   ct++;
           j++;                  
        }
}
	std::cout << ct;
}


your multiply on the inner loop only applies to the condition in the while. the code inside the while is not multiplied there.
Last edited on
But excuse me you think that it isn't right??
See this
at page 10 number 4
http://www-db.deis.unibo.it/courses/FIL-B/Lezioni/complessita.pdf
It is in italian language , it is the same exercise...
I no longer have an opinion of right or wrong. I am just letting you see how many times the cout statement would execute if N were 100. If you still believe you are correct, then hand it in. Its entirely possible I am not right but your 3n^2+1 sure seems high to me. If N is 100, that implies that 30001 things happened. I am not seeing a count this high, but I am not familiar with whatever you are trying to do, either.

a c++ level operation-count, I get:
int i;
int j = 0;
int n = 100; //3
int ct = 0;

for (i=1; i<n; i++) //n-1
{
while (j<n) //n-1 + n
{
//cout <<a;
ct++; //n
j++; //n
}
}
std::cout << ct;
}

(2n-2) + 3n +3 = 5n +1 = 501 for n = 100.
which may be off slightly, I am confusing myself on the activated while loop one time execution a little. But its a long way from 30k.
Last edited on
Topic archived. No new replies allowed.