Big O notation
- Thread starter K.I.L.E.R
- Start date
At first I didn't get how you could think that, but then I realized the misunderstanding.OpenGL guy said:If anyone here disagrees that f= n^2 is O(1) then I'll be very confused.
You're talking about the complexity to calculate the function f
, but what we're talking about here is when f is the complexity of some algorithm.So f
= n^2 is O(n^2), but the time it takes to calculate f is O(1) (kind of, see DemoCoder's post).bloodbob:
You have some small calculation errors in post #10 and #12 (constants, and signs). And a bigger one in the final step in post #12. Considering the small steps you took between the first steps, it's a major leap to say that "n^3+(2n-1)+(4n-4)+(6n-9)..." is O(n^3). It seems like you missed the negative n^3 term in it.
It wouldn't have mattered if the "(2n-1)+(4n-4)+(6n-9)..."-part could be neglected.bloodbob said:
(Btw, it should've been n^3-(2n-1)-(4n-4)-(6n-9)...)
And you're right that the misstake isn't -n^3. It's -2/3*n^3 + O(n^2). So the conclusion is corrrect, except that you shouldn't draw that conclusion without proving that the "-2/3"-part isn't -1.
Sorry for nitpicking, it's an "occupational injury" from all the math exams I've marked.
The former just isn't right. Big O is always about algorithmic complexity. Every f(x) that can be expressed wholly without Sigma or Pi (accumulation, successive multiplication) is always O(1). That includes all functions used as examples in this thread so far.Basic said:So f
What you're doing there is polynomial classification. f(x)=x² is a second order polynomial function. But you don't use big O notation for that, that's just confusing.
Here's a math type friendly example for O notation:
a(0):=1
a(n+1):=a
*2, n>=0O
=n, because if you want to compute the 1000th element, you need to do 1001 operations, 2001 ops for #2000 etc. Number of ops scales "almost" linearly with n. That's what this notation is about.If you were going to classify this, you'll quickly see that a
=2^n.And then you could go ahead with this insight and optimize the "algorithm" by simplification, making it O(1), because it is, again, only a single term.
Last edited by a moderator:
I took his fOpenGL guy said:If anyone here disagrees that f
as the full complexity not as the actual function since he said
.I understand you take out the multiplier of the largest growing function, and stick the fastest growing part inside a Big O
f
Big O:
f
Clearly you could have cases where you could have such a complexity.
Code:
main()
{
n=1000;
recurse(1000);
}
recurse( int n )// complexity =n^2-f(n-1)
{
if( n > 0 )
{
for( int outer=0;outer<n;outer++) //n^2 for loops
for( int inner=0;innter<n;inner++)
do something;
}
recurse( n-1); // f(n-1)
};Edit:n=problem size if it was x^2 then that would be O(1)
So frankly I do disagree since otherwise all I learnt at univeristy was for nothing.
And for a dataset of n if the complexity is n^2+(n-1)^2+(n-1)^2+..+(n-[n-1])^2 steps the order of complexity should be O(n^3). Its not O(n^2) due to the fact that the complexity formula that kiler gave us is depedant on the value of n.
If I was wrong about kiler's meaning then it should be O
since you have n recursions and a constant number of steps in each recursion though you could optimise the algorithim to be O(1).
Last edited by a moderator:
arjan de lumens
Veteran
I seem to remember rather clearly from the mathematics that I have studied that the Big-O notation is frequently used in calculus and discrete mathematics also outside just algorithmic complexity measurements.zeckensack said:
When trying to look up the Big-O notation at e.g. Mathworld, i found:
http://mathworld.wolfram.com/AsymptoticNotation.html which seems to define it only in terms of functions, not algorithms. From what I can find, the notation is not invented specifically to deal with algorithmic complexity - it is merely very convenient to use for that purpose.
I must admit I'm a bit rusty, but I don't recall ever seeing that applied. I strictly associate O(whatever) to computer science, because during the math lessons I took (including only four "basic" semesters at university, because I didn't require more; might be different later on) there was always a different way to express what you "allow" as another meaning of Oarjan de lumens said:
notation: limes.E.g. for f(x):=3*x³-x, lim(f(x)) for x->infinity is 3*x³ or, more colloquial, f(x) approaches 3*x³ toward infinity. Using that, there's no need for using O
in this context, which I find very confusing, so I like being able to avoid it, even though I now see that it is common in some places.The "problem" with the limes is that it does not eliminate constant factors, like 3 in my example. "Your" O
of that function would be x³ (or n³ or whatever) while "my" limes is 3*x³. So it's not the same but close enough.
Barring arjan de lumens and my reply ... I think this is about algorithmic complexity, because of the code
:=n² does not take n² operations to compute. It takes exactly one operation, regardless of how big n is. Even for f:=10*n², which takes two operations, O is still 1, not 2, because the number of operations does not grow with larger n.
Bubble sort OTOH does take a growing amount of operations depending on the size of the field to be sorted (which is n aka "the size of the problem" btw), so it must have O dependent on n itself. Dunno if it's n² but that looks pretty reasonable.
. You compute 1² for #1, square and add 2² for #2, square and add 3² for #3 etc. For each consecutive element, you do two operations extra (except for the first element). I.e. the number of req'd operations grows linearly with n.
The value of the term does grow much faster, but that's a separate issue.
OpenGL guy said:If anyone here disagrees that f
fbloodbob said:
:=n² does not take n² operations to compute. It takes exactly one operation, regardless of how big n is. Even for f:=10*n², which takes two operations, O is still 1, not 2, because the number of operations does not grow with larger n.Bubble sort OTOH does take a growing amount of operations depending on the size of the field to be sorted (which is n aka "the size of the problem" btw), so it must have O
dependent on n itself. Dunno if it's n² but that looks pretty reasonable.I say it's Obloodbob said:
. You compute 1² for #1, square and add 2² for #2, square and add 3² for #3 etc. For each consecutive element, you do two operations extra (except for the first element). I.e. the number of req'd operations grows linearly with n.The value of the term does grow much faster, but that's a separate issue.
Yes.bloodbob said:If I was wrong about kiler's meaning then it should be O
Did you even bother to read???zeckensack said:Barring arjan de lumens and my reply ... I think this is about algorithmic complexity, because of the code
I took his f
When he said f
:=n^2-f(n-1) he ment Complexity(f)=n^2+Complexity(f(n-1)).Seriously if you looked at the code I posted I can't se how in hell you could do that in n steps your deluded.
and how can you say something that takes "n^2+(n-1)^2+(n-1)^2+..+(n-[n-1])^2" steps is order O
??????? you've quoted that text and then said you think thats O simply doing what kiler did and looking at the largest term its clearly atleast O(n^2)
Last edited by a moderator:
Yes. I misunderstood some parts. In particular, I lost you when you added up complexities terms, not value terms. And so I also couldn't relate your code snippet to anything above, but rather thought it was a new example for a high complexity algorithm. My apologies. There is a point that still stands though.bloodbob said:
OpenGL guy might have misunderstood something, too, but what he said was correct in itself. I read your previous post as disagreeing with him, and thought you misunderstood him as well. From earlier:
He didn't make that claim. That was why I thought you misunderstood, and why I wrote my reply.bloodbob said:
It's easy to get confused when what is written is not what is meant. And just as frankly, I don't see how you reach that interpretation from what K.I.L.E.R originally asked, to which the answer is Obloodbob said:When he said f
ito algorithmic complexity without a doubt in my mind.First he uses fzeckensack said:It's easy to get confused when what is written is not what is meant. And just as frankly, I don't see how you reach that interpretation from what K.I.L.E.R originally asked, to which the answer is O
and O, n is the size of the problem size. O is obivously order of complexity and well f generally just means function so what would be a function of the problem size? well it would obiviously be the complexity/term function. This is the only logical answer so if I'm wrong I blame kiler.I'd hope that kiler has some basic idea of the order of complexity actually relates to complexity. So when his talking about the largest "growing function"/term he is talking about complexity. So when he then and goes and pulls out n^2 from f
it would also indicate that f is the complexity.Maybe I'm just crazy.
Last edited by a moderator:
OpenGL guy
Veteran
I don't read it that way at all. For example, KILER could have been giving a function that determines a series where it makes more sense to use "n" as your variable instead of "x".bloodbob said:First he uses f
Jury's still out on that one
Anyway, without some more feedback from KILER (like what context is this taken from), this whole thing is kinda moot. I still feel that people are making this way too complicated...
I'm talking about algorithmic functions and not mathametical ones.
I'm bringing a computer algorithm down into a math function and measuring it's complexity in O.
I think I'm understanding this a lot better.
I'm looking for a conclusive answer to this because I wish to apply this knowledge to a few algorithms I have.
I'm bringing a computer algorithm down into a math function and measuring it's complexity in O.
I think I'm understanding this a lot better.
I'm looking for a conclusive answer to this because I wish to apply this knowledge to a few algorithms I have.
Clarification please. Are youK.I.L.E.R said:
A) Your bring the algorithm down to a math function
Or
B) Are you bring down the number of steps need for an algorithm down to a math function.
If A) then an code for the thing you posted up the top would be
Code:
int recurse( n )
{
return n^2+recurse( n-1);
}B) it could be something like this
Code:
recurse( n )
{
for( int outter=0;outter<n;outter++)
{[indent]for( int inner=0;inner<n;inner++)
{
doSomething(outter,inner,n);
};
[/indent]};
recurse( n-1 );
return;
}
//this isn't needed but I'll put it anyway
doSomething(int x,int y,int z)
{
someglobalarray[z][y][x]=someglobalarray[z][y][x]^2-someotherglobalarray[z][y][x];
// Yeah I'm a dirty C bastard who wirtes bad code
}
Last edited by a moderator:
Well then your just silly for using f(n) and OK.I.L.E.R said:A.
together and confusing me.Then its O
( n loops of a constant number of steps) because of your bad implementation.http://www.shu.edu/projects/reals/infinity/answers/sm_sq_cb.html
Is a better implementation which will take a constant number of step so it will be O(1).
I over estimated your knowledge here :/
Similar threads
