need complexity pleaseee!!!

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("%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);
}
}

---

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.

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...

Quote:

---

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

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

anybody????

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

yes....

Quote:

---

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.

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!...

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)

Quote:

---

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.

Quote:

---

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)....

Quote:

---

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

Quote:

---

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)

Quote:

---

Originally Posted by Govalant

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

---

Well, no, it's O(n), I was trying to make a mathematical point, not a complexity one...

QuantumPete

Quote:

---

Originally Posted by QuantumPete

Well, no, it's O(n), I was trying to make a mathematical point, not a complexity one...

QuantumPete

---

It's not O(n) either, you can't know how the algorithm will behave, for now, all i know is that if n is a power of 2, the complexity will be O(log2(n))

I'm coding something right now to analyze it.

EDIT: here, look at the complexity plot of the 3n+1 problem

http://img258.imageshack.us/img258/5613/plotpv7.jpg


The average iteration number from 1 to 256 is 44.98046875.

http://en.wikipedia.org/wiki/Collatz_conjecture