A program to compute for Big Oh
-
Good Day, Is there a program that can compute for Big Oh notations? I mean, I just paste the code segment and it will generate the Big Oh notation for that segment. Thanks! :-D
It is said that the most complex structures built by mankind are software systems. This is not generally appreciated because most people cannot see them. Maybe that's a good thing because if we saw them as buildings, we'd deem many of them unsafe.
-
Good Day, Is there a program that can compute for Big Oh notations? I mean, I just paste the code segment and it will generate the Big Oh notation for that segment. Thanks! :-D
It is said that the most complex structures built by mankind are software systems. This is not generally appreciated because most people cannot see them. Maybe that's a good thing because if we saw them as buildings, we'd deem many of them unsafe.
I thought you were talking about me here. (My nickname at school was the Big O - being 6 foot at 13 year old).
Deja View - the feeling that you've seen this post before.
-
Good Day, Is there a program that can compute for Big Oh notations? I mean, I just paste the code segment and it will generate the Big Oh notation for that segment. Thanks! :-D
It is said that the most complex structures built by mankind are software systems. This is not generally appreciated because most people cannot see them. Maybe that's a good thing because if we saw them as buildings, we'd deem many of them unsafe.
Not sure if there is one, but it wouldn't be that hard to implement :)
"The clue train passed his station without stopping." - John Simmons / outlaw programmer "Real programmers just throw a bunch of 1s and 0s at the computer to see what sticks" - Pete O'Hanlon
-
Not sure if there is one, but it wouldn't be that hard to implement :)
"The clue train passed his station without stopping." - John Simmons / outlaw programmer "Real programmers just throw a bunch of 1s and 0s at the computer to see what sticks" - Pete O'Hanlon
Paul Conrad wrote:
but it wouldn't be that hard to implement
So what would the output be for this function?
int F(int n)
{
// assume n > 0
int c = 0;
while (n != 1) {
if ((n % 2) == 1) // n odd
n = 3 * n + 1;
else // n even
n = n / 2;
c++;
}
return c;
} -
Paul Conrad wrote:
but it wouldn't be that hard to implement
So what would the output be for this function?
int F(int n)
{
// assume n > 0
int c = 0;
while (n != 1) {
if ((n % 2) == 1) // n odd
n = 3 * n + 1;
else // n even
n = n / 2;
c++;
}
return c;
}Your function is of O(n)...
"The clue train passed his station without stopping." - John Simmons / outlaw programmer "Real programmers just throw a bunch of 1s and 0s at the computer to see what sticks" - Pete O'Hanlon
-
Your function is of O(n)...
"The clue train passed his station without stopping." - John Simmons / outlaw programmer "Real programmers just throw a bunch of 1s and 0s at the computer to see what sticks" - Pete O'Hanlon
Do you have a proof for that? You might want to read http://en.wikipedia.org/wiki/Collatz_conjecture[^] Edit: maybe you are right, I should have written BigInteger instead of int...
-
Do you have a proof for that? You might want to read http://en.wikipedia.org/wiki/Collatz_conjecture[^] Edit: maybe you are right, I should have written BigInteger instead of int...
The line count through the execution does bounce fluctuate like the graph on the wiki article. Throwing the values into a excel spreadsheet and doing a trendline and equation is rather sketchy.
"The clue train passed his station without stopping." - John Simmons / outlaw programmer "Real programmers just throw a bunch of 1s and 0s at the computer to see what sticks" - Pete O'Hanlon
-
The line count through the execution does bounce fluctuate like the graph on the wiki article. Throwing the values into a excel spreadsheet and doing a trendline and equation is rather sketchy.
"The clue train passed his station without stopping." - John Simmons / outlaw programmer "Real programmers just throw a bunch of 1s and 0s at the computer to see what sticks" - Pete O'Hanlon
It's O(n) only if it terminates at all. Which is still unproven. What happened to your first answer? It disappeared and took my response with it. I won't repeat it here, but basically I think that even if you restrict yourself to terminating programs, you can construct cases where the running time can be determined only by solving some unsolved math problem.
-
It's O(n) only if it terminates at all. Which is still unproven. What happened to your first answer? It disappeared and took my response with it. I won't repeat it here, but basically I think that even if you restrict yourself to terminating programs, you can construct cases where the running time can be determined only by solving some unsolved math problem.
Original post was a bit off. Seems like no one knows for sure if the Collatz Conjecture does. I remember my algorithms teacher talking about it. If there were to be a program that you could just feed in a code snippet and it returns whatever the Big O is for the code snippet, one would have to make the assumption the code does terminate and is in simple form. This would have to lead into defining what is actually simple?
"The clue train passed his station without stopping." - John Simmons / outlaw programmer "Real programmers just throw a bunch of 1s and 0s at the computer to see what sticks" - Pete O'Hanlon