need complexity pleaseee!!!

[kwdikosno8]

have this problem-->
http://online-judge.uva.es/p/v1/100.html
can someone help me find the complexity of my solution...i need step by step help how can i find the complexity
thnks in advanceeeeeeeeeeeeeeeeeee

#include "stdio.h"
void main(){
long n,i,temp,n0,n1,master_number,c=1;
while (scanf("%ld %ld",&n0,&n1)!=EOF)
 {

	printf ("%ld %ld ",n0,n1);

	master_number=1;

	if (n0>n1)                            
	{
		temp=n0;n0=n1;n1=temp;
	}
    for (i=n0;i<=n1;i++)           
	{
        c=1;n=i;
       while(n>1)
	   {
	      n=(n%2)?(3*n+1):(n/2);
          c++;
	   }
      if (c>master_number) 
	  {
		  master_number=c;
	  } 
	}
printf ("%ld\n",master_number);
}
}

[Happy_Reaper]

Are you sure that even prints out the output you desire ?

And for complexity, how about you walk us through what you think the complexity is and why, and we'll tell you if and where you went wrong.

[kwdikosno8]

i am sure that the code is correct...
now i think that i have to find the complexity of the fist if..
then find the complexity of the for loop
and then find the last if complexity

finally i have to sum these...
is this the right way?
and how can i find these complexitys?
really have no idea!

thnks in advance for any help...

[ZuK]

i am sure that the code is correct...

nobug.c: In function 'main':
nobug.c:21: error: expected ':' before 'n'
nobug.c:21: error: expected statement before ')' token
nobug.c:2: warning: return type of 'main' is not 'int'

Kurt

[kwdikosno8]

copy paste problem...now is correct ( i think )

[kwdikosno8]

anybody????

[sujeet1]

when u say complexity are u refering to the big O notation ?
like O (1) O (n square ) O(n) and stuff>

[kwdikosno8]

yes....

[laserlight]

copy paste problem...now is correct ( i think )

Unfortunately your code is still badly indented and retains void main().

Considering that it is not known if the algorithm will terminate (i.e., it may not even be an algorithm), it seems to me that its average and worst case complexity is not known.

Disclaimer: I am still somewhat hopelessly confuzzled by complexity beyond the textbook searching/sorting examples.

[kantze]

Well here is an idea: The problem says that all the numbers will be between 1 and 1.000.000. If you run your program (which works right) and type "1 1000000", without quote,
it prints 476.

Note that 476 other than the maximum cycle length is a counter that metres how many times multiplication(or division) occurs.

So , you start saying that:
the basic operation of the problem is multiplication of the innermost loop

.....
       while(n>1)
	   {
	      n=(n%2)?(3*n+1):(n/2); // <--- HERE
          c++;
	   }
....

By testing the program I saw that this multiplication occurs at most, 476 times.
So surely it does less multiplications than an algorithm that would do 476 multiplications for each number.
So my problem's complexity is less than (n1 - n0 +1) * 476 ....
I know this "solution" is bad, and I don't know if it even is acceptable.

That's the best I thought!...

[kantze]

Can anyone please tell me if the above answer is somehow acceptable??

Can we then say: The input size of the problem is the the numbers between n0 and n1, so
n = n1-n0+1 so ,and as a result(from the previous answer) the order of growth of the problem is less than n * 476 ----> Complexity is O(n)

[Govalant]

Can anyone please tell me if the above answer is somehow acceptable??

Can we then say: The input size of the problem is the the numbers between n0 and n1, so
n = n1-n0+1 so ,and as a result(from the previous answer) the order of growth of the problem is less than n * 476 ----> Complexity is O(n)

But you still need to check all the numbers to find the maximum.

So it would the complexity of all the numbers (n) multiplied by the complexity of running the 3n+1 algorithm.

And for what i think, you can´t know how the algorithm will behave. That's what you need to figure out, but i woudn't bet on it, i'm not in college yet.

[kantze]

But you still need to check all the numbers to find the maximum.

So it would the complexity of all the numbers (n) multiplied by the complexity of running the 3n+1 algorithm.

And for what i think, you can´t know how the algorithm will behave. That's what you need to figure out, but i woudn't bet on it, i'm not in college yet.

Yes, you're probably right!

SO, instead of running the program can we say that?

Let the maximum number of multiplications on each iteration be max ( If we ran it , we would know it is 476).

The order of of growth of the problem is less than max * n ( where max is a constant)
so, the complexity is O(n).

Is it OK ? Or, still , max can be n , or +oo and this allegation is wrong(or very abstract)....

[QuantumPete]

So it would the complexity of all the numbers (n) multiplied by the complexity of running the 3n+1 algorithm.

Erm, I would say that in that case you're looking at:
n * (3n+1) = 3n^2 + n
And since we regard only the biggest polynomial (save for logs) you'd get O(n^2)...

QuantumPete

[Govalant]

Erm, I would say that in that case you're looking at:
n * (3n+1) = 3n^2 + n
And since we regard only the biggest polynomial (save for logs) you'd get O(n^2)...

QuantumPete

The complexity of the 3n + 1 algorithm is not O(3n + 1)