|
Thread Rules
1. This is not a "do my homework for me" thread. If you have specific questions, ask, but don't post an assignment or homework problem and expect an exact solution.
2. No recruiting for your cockamamie projects (you won't replace facebook with 3 dudes you found on the internet and $20)
3. If you can't articulate why a language is bad, don't start slinging shit about it. Just remember that nothing is worse than making CSS IE6 compatible.
4. Use [code] tags to format code blocks. |
On August 11 2013 07:46 darkness wrote:
for (int i = 10; i < 2000; i+= 10)
{
for (int j = 1; j < 2000; j++)
{
DoSomethingWithPixel(i, j);
DoSomethingWithPixel(j, i);
}
}
How is this not O(N^2)? As far as I remember, nested loop is O(N^2) or O(N^3) if you have 3 loops inside each other.
This is O(N^2), you are right.
On August 11 2013 07:44 Morfildur wrote:Show nested quote +On August 11 2013 07:38 CecilSunkure wrote:On August 11 2013 07:35 Morfildur wrote:On August 11 2013 06:38 Shenghi wrote:
The minor optimization discussed here is turning an algorithm from O(N^2) to O(N^2), losing a bunch of readability in the process. The O(N^2) is a notation of complexity, not performance. for (i = 0; i < 1000;++i)
for (i = 0; i < 100; ++i)
Both are O(1) but the second is still preferrable whenever possible. Just because they are both O(1) doesn't mean that one can't be better than the other. The code being discussed makes the execution 10 times faster, so that is not a minor optimization. Depending on the context it can be a huge difference for a really, really, really tiny loss of readability. That's O(N)  N is 1000, then 100. Depends. The 1000 is a constant, it never changes. Constant execution time is O(1). If the 1000 was passed in via a variable, it would be O(N), i.e. scales linarly. The 100 is not related to the 1000 before, so it's in itself O(1) as well. In the case of void foo(int x)
{
for (int i = 0; i < x; ++i) { }
}
foo(1000);
foo(100);
it would be O(N) Then again, that is just my interpretation. Might be that comp sci people disagree with it. I never cared much about the theory of that stuff since it has no connection to real programming anyways.
Big O notation is to describe loop complexity. There's a huge difference in the complexity of these loops:
for(uint32 i = 0; i < 10; i++)
{
...
}
for(uint32 i = 0; i < 10; i++)
{
for(uint32 j = 0; j < 20; j++)
{
...
}
}
Both of these loops use "static integrals" for their loop, so yes the number of cycles is known. However when describing the loops, saying both are O(1) gives no valuable information. However if you describe them with proper big O notation, you can say something valuable about the complexity of each.
|
Is it really n^2?
Here N would be 2000, the outer loops only runs 200 times, and the inner 2000, so it would be more like (N^2)/10
e: yea I guess you normally notate it without constant coefficients
|
On August 11 2013 07:53 Yoshi- wrote:
Is it really n^2?
Here N would be 2000, the outer loops only runs 200 times, and the inner 2000, so it would be more like (N^2)/10
For Big O notation, the /10 is irrelevant.
|
On August 11 2013 07:53 Yoshi- wrote:
Is it really n^2?
Here N would be 2000, the outer loops only runs 200 times, and the inner 2000, so it would be more like (N^2)/10
e: yea I guess you normally notate it without constant coefficients
There's no such thing as O(N^2)/10, it just devolves into O(N^2). There are only a few categories of complexities, and extra cruff is just "truncated".
|
Hyrule19264 Posts
On August 11 2013 07:44 Morfildur wrote:Show nested quote +On August 11 2013 07:38 CecilSunkure wrote:On August 11 2013 07:35 Morfildur wrote:On August 11 2013 06:38 Shenghi wrote:
The minor optimization discussed here is turning an algorithm from O(N^2) to O(N^2), losing a bunch of readability in the process. The O(N^2) is a notation of complexity, not performance. for (i = 0; i < 1000;++i)
for (i = 0; i < 100; ++i)
Both are O(1) but the second is still preferrable whenever possible. Just because they are both O(1) doesn't mean that one can't be better than the other. The code being discussed makes the execution 10 times faster, so that is not a minor optimization. Depending on the context it can be a huge difference for a really, really, really tiny loss of readability. That's O(N) N is 1000, then 100. Depends. The 1000 is a constant, it never changes. Constant execution time is O(1). If the 1000 was passed in via a variable, it would be O(N), i.e. scales linarly. The 100 is not related to the 1000 before, so it's in itself O(1) as well. In the case of void foo(int x)
{
for (int i = 0; i < x; ++i) { }
}
foo(1000);
foo(100);
it would be O(N) Then again, that is just my interpretation. Might be that comp sci people disagree with it. I never cared much about the theory of that stuff since it has no connection to real programming anyways.
Neither of those is O(1), they are both O(n).
Example of O(1): cout << some_array[6];
|
On August 11 2013 07:47 CecilSunkure wrote:Show nested quote +On August 11 2013 07:46 darkness wrote:
for (int i = 10; i < 2000; i+= 10)
{
for (int j = 1; j < 2000; j++)
{
DoSomethingWithPixel(i, j);
DoSomethingWithPixel(j, i);
}
}
How is this not O(N^2)? As far as I remember, nested loop is O(N^2) or O(N^3) if you have 3 loops inside each other. This is O(N^2), you are right. Show nested quote +On August 11 2013 07:44 Morfildur wrote:On August 11 2013 07:38 CecilSunkure wrote:On August 11 2013 07:35 Morfildur wrote:On August 11 2013 06:38 Shenghi wrote:
The minor optimization discussed here is turning an algorithm from O(N^2) to O(N^2), losing a bunch of readability in the process. The O(N^2) is a notation of complexity, not performance. for (i = 0; i < 1000;++i)
for (i = 0; i < 100; ++i)
Both are O(1) but the second is still preferrable whenever possible. Just because they are both O(1) doesn't mean that one can't be better than the other. The code being discussed makes the execution 10 times faster, so that is not a minor optimization. Depending on the context it can be a huge difference for a really, really, really tiny loss of readability. That's O(N) N is 1000, then 100. Depends. The 1000 is a constant, it never changes. Constant execution time is O(1). If the 1000 was passed in via a variable, it would be O(N), i.e. scales linarly. The 100 is not related to the 1000 before, so it's in itself O(1) as well. In the case of void foo(int x)
{
for (int i = 0; i < x; ++i) { }
}
foo(1000);
foo(100);
it would be O(N) Then again, that is just my interpretation. Might be that comp sci people disagree with it. I never cared much about the theory of that stuff since it has no connection to real programming anyways. Big O notation is to describe loop complexity. There's a huge difference in the complexity of these loops: for(uint32 i = 0; i < 10; i++)
{
...
} for(uint32 i = 0; i < 10; i++)
{
for(uint32 j = 0; j < 20; j++)
{
...
}
} Both of these loops use "static integrals" for their loop, so yes the number of cycles is known. However when describing the loops, saying both are O(1) gives no valuable information. However if you describe them with proper big O notation, you can say something valuable about the complexity of each.
Almost everything in your post is wrong.
Big O notation is a mathematical concept way more general than just describing "loop complexity".
It can, of course, be generalized to more advanced algorithms than loops. See:
http://en.wikipedia.org/wiki/Big_O_notation
In the examples you quoted, there is only one loop which iterates a variable number of times.
Nesting loops does not necessarily increase complexity in that sense.
for (int i = 10; i < 2000; i+= 10)
{
for (int j = 1; j < 2000; j++)
{
DoSomethingWithPixel(i, j);
DoSomethingWithPixel(j, i);
}
}
The code in the inner loop will run a total of 1999*199 times which is a constant number.
Complexity in big O notation is thus: 1999*199 times the complexity of the DoSomethingWithPixel(x,y) function.
If and only if this is an operation that runs in constant time, then the complexity of the whole thing is O(1).
|
That's not what I was taught in the context of computer science. That code drawing pixels has a complexity of O(N^2).
Edit: Technically, since the loop bounds are known you can treat the whole thing as a single operation, making it O(1). But really those 2000 bounds are just hard coded N. It depends on what you consider N as.
|
On August 11 2013 04:38 darkness wrote:Show nested quote +On August 11 2013 03:20 bangsholt wrote:But why would you do that You'll just take the runtime from "not very long" to "a bit less than not very long", and now it is not obvious why you are skipping it  Unless the run time is a problem, you should not optimize. If you do optimize, run a profiler and figure out where you should optimize. You are almost always wrong in your guesses with where to optimize. Clearness of code is as important if not more important than speed, as it's hard to achieve better speed if you do not know what is going on. Any "a bit less than not very long" is better than "not very long". If something isn't clear, you always have /* comments */, right? I don't really agree with your thinking. After all, one of Software Engineering's goals is efficiency, in particular not to waste system resources.
Premature optimization is the root of many evil things in software development.
The "optimization" may make sense in your head, and it may make sense in the comments, until the code is updated and the comment is not. Now instead of readable code, you have that may very well contradict the comment.
This is why you don't optimize before you know you need to.
But of course, as we all know, we live in a perfect world and the scenario I described cannot possibly happen :D
|
On August 11 2013 08:36 CecilSunkure wrote:
That's not what I was taught in the context of computer science. That code drawing pixels has a complexity of O(N^2).
Exactly. People who argue nested loop can in any case be O(1) or anything less than O(N^2) need to re-read about Big O.
|
On August 11 2013 08:45 darkness wrote:Show nested quote +On August 11 2013 08:36 CecilSunkure wrote:
That's not what I was taught in the context of computer science. That code drawing pixels has a complexity of O(N^2). Exactly. People who argue nested loop can in any case be O(1) or anything less than O(N^2) need to re-read about Big O.
I don't know about you, but I am a computer scientist.
You are just wrong.
|
On August 11 2013 08:47 one-one-one wrote:Show nested quote +On August 11 2013 08:45 darkness wrote:On August 11 2013 08:36 CecilSunkure wrote:
That's not what I was taught in the context of computer science. That code drawing pixels has a complexity of O(N^2). Exactly. People who argue nested loop can in any case be O(1) or anything less than O(N^2) need to re-read about Big O. I don't know about you, but I am a computer scientist. You are just wrong.
On August 11 2013 08:36 CecilSunkure wrote:
Edit: Technically, since the loop bounds are known you can treat the whole thing as a single operation, making it O(1). But really those 2000 bounds are just hard coded N. It depends on what you consider N as.
|
On August 11 2013 08:45 darkness wrote:Show nested quote +On August 11 2013 08:36 CecilSunkure wrote:
That's not what I was taught in the context of computer science. That code drawing pixels has a complexity of O(N^2). Exactly. People who argue nested loop can in any case be O(1) or anything less than O(N^2) need to re-read about Big O.
Big O is used to describe algorythms, and not loops, this loop is constant so it is O(1), if it were a variable limit than you could say that it is n^2
And ofc in this context using it makes no sense anyway, so why even bring this up
|
It's O(N) because the complexity scales linearly with the number of pixels. Doubling the number of pixels in the x or y dimension doubles the number of DoSomethingWithPixel() calls.
On August 11 2013 08:33 one-one-one wrote:
The code in the inner loop will run a total of 1999*199 times which is a constant number.
Complexity in big O notation is thus: 1999*199 times the complexity of the DoSomethingWithPixel(x,y) function.
If and only if this is an operation that runs in constant time, then the complexity of the whole thing is O(1).
You're right in that the number of loops doesn't necessarily correspond to the complexity of the algorithm, but big O notation isn't usually understood in that way. If it were, iteration over a fixed length array would be considered constant time.
|
On August 11 2013 08:49 CecilSunkure wrote:Show nested quote +On August 11 2013 08:47 one-one-one wrote:On August 11 2013 08:45 darkness wrote:On August 11 2013 08:36 CecilSunkure wrote:
That's not what I was taught in the context of computer science. That code drawing pixels has a complexity of O(N^2). Exactly. People who argue nested loop can in any case be O(1) or anything less than O(N^2) need to re-read about Big O. I don't know about you, but I am a computer scientist. You are just wrong. Show nested quote +On August 11 2013 08:36 CecilSunkure wrote:
Edit: Technically, since the loop bounds are known you can treat the whole thing as a single operation, making it O(1). But really those 2000 bounds are just hard coded N. It depends on what you consider N as.
No. For some function to be O( n ) or O(n^2) (whatever) , there has to be a 'n' that is a variable.
Either you have that or you don't.
Anything else is confusion and misunderstanding on your end.
|
On August 11 2013 08:53 one-one-one wrote:Show nested quote +On August 11 2013 08:49 CecilSunkure wrote:On August 11 2013 08:47 one-one-one wrote:On August 11 2013 08:45 darkness wrote:On August 11 2013 08:36 CecilSunkure wrote:
That's not what I was taught in the context of computer science. That code drawing pixels has a complexity of O(N^2). Exactly. People who argue nested loop can in any case be O(1) or anything less than O(N^2) need to re-read about Big O. I don't know about you, but I am a computer scientist. You are just wrong. On August 11 2013 08:36 CecilSunkure wrote:
Edit: Technically, since the loop bounds are known you can treat the whole thing as a single operation, making it O(1). But really those 2000 bounds are just hard coded N. It depends on what you consider N as. No. For some function to be O( n ) or O(n^2) (whatever) , there has to be a 'n' that is a variable. Either you have that or you don't. Anything else is confusion and misunderstanding on your end.
Dude you're being an asshole. You can consider N as different things in the situation... You're not helping anyone here.
Think of it this way: you can hard code a variable in your code, and theoretically it is a variable, just a poorly coded and represented one. In the case of drawing pixels, you can consider the integral constants as hardcoded N variables, or not. It doesn't matter either way as long as you're clear on what N is.
|
On August 11 2013 08:54 CecilSunkure wrote:Show nested quote +On August 11 2013 08:53 one-one-one wrote:On August 11 2013 08:49 CecilSunkure wrote:On August 11 2013 08:47 one-one-one wrote:On August 11 2013 08:45 darkness wrote:On August 11 2013 08:36 CecilSunkure wrote:
That's not what I was taught in the context of computer science. That code drawing pixels has a complexity of O(N^2). Exactly. People who argue nested loop can in any case be O(1) or anything less than O(N^2) need to re-read about Big O. I don't know about you, but I am a computer scientist. You are just wrong. On August 11 2013 08:36 CecilSunkure wrote:
Edit: Technically, since the loop bounds are known you can treat the whole thing as a single operation, making it O(1). But really those 2000 bounds are just hard coded N. It depends on what you consider N as. No. For some function to be O( n ) or O(n^2) (whatever) , there has to be a 'n' that is a variable. Either you have that or you don't. Anything else is confusion and misunderstanding on your end. Dude you're being an asshole. You can consider N as different things in the situation... You're not helping anyone here.
Lol.
There is no argument here. It is the most obvious case you can get.
Just check the definition.
I'm an asshole for pointing that out?
You are being ignorant and rude.
edit: people like you are the reason why this is a common misconception.
|
Edit: Looks like all receivable points have been made here. We're just arguing semantics, computer scientists vs programmers :D
And anyway, all of your examples are in P, so they're easy. Trololol :p
|
Oh my god, what have i started.
Does it really matter? Let's just agree that it's O(N) with N being 1 and both sides are right.
|
On August 11 2013 09:06 Morfildur wrote:
Oh my god, what have i started.
Does it really matter? Let's just agree that it's O(N) with N being 1 and both sides are right.
Yes, they are both right, which is what we've been saying 
|
This is really a non-discussion.
I don't understand why anyone would try to make any sense out of applying big O notation to code like
while( i < CONSTANT )
while (j < ANOTHER_CONSTANT)
doSomethingRequiringConstantTimeRegardlessofInputs( x,y )
sure if you change your screen resolution often or use the program on devices with different resolutions you might have a case, but the money argument here is not about complexity in a big O notation sense ; it is about the total number of operations.
What you want is to reduce overhead as much as possible by removing unnecessary operations.
You might find a routine that does the job in 5ms instead of 25ms , but has a worse time complexity as a function of XRES and YRES. (Which might be dependent and baked together as some kind of N, yes)
This happens in programming projects all the time.
|
|
|
|
|
|
EPT
