need complexity pleaseee!!!

**kwdikosno8** · 09-08-2007

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

Code:

#include "stdio.h"
void main(){
long n,i,temp,n0,n1,master_number,c=1;
while (scanf("&#37;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** · 09-08-2007

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** · 09-08-2007

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** · 09-08-2007

Originally Posted by kwdikosno8

i am sure that the code is correct...

Code:

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** · 09-08-2007

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

)

**kwdikosno8** · 09-09-2007

anybody????

**sujeet1** · 09-09-2007

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

**kwdikosno8** · 09-09-2007

yes....

**laserlight** · 09-09-2007

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** · 09-09-2007

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

Code:

.....
       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** · 09-09-2007

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** · 09-09-2007

Originally Posted by 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)

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** · 09-09-2007

Originally Posted by Govalant

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** · 09-09-2007

Originally Posted by Govalant

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** · 09-09-2007

Originally Posted by QuantumPete

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)

Thread: need complexity pleaseee!!!

Thread Tools

Search Thread

Display

need complexity pleaseee!!!

Similar Threads

Complexity

Algorithm Complexity

Worst-case complexity of this function?

question on time complexity

Algorithm - Complexity.