Big Oh Computation
-
So as you can see now. When you nest loops you multiply the complexity. When you have loops side by side, you add.
When you say we add, that means N+N+N or simply 3N. Correct me if I'm wrong but there is no such thing as O(3N) but only O(N)?
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.
-
When you say we add, that means N+N+N or simply 3N. Correct me if I'm wrong but there is no such thing as O(3N) but only O(N)?
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.
That's exactly correct, on both counts.
-
So as you can see now. When you nest loops you multiply the complexity. When you have loops side by side, you add.
leppyr64 wrote:
When you nest loops you multiply the complexity.
If the number of iterations on an inner loop is proportional to the size of the problem, and will be the same for all iterations of the outer loop, then the complexity of the outer loop is a factor of N greater than that of the inner loop. The same will be true if the number of iterations for the inner loop will be uniformly distributed over a range, the top of which is proportional to the size of the problem. There will be occasions, however, where nested loops aren't nearly as bad as they appear because, while the worst-case time of the inner loops is proportional to the size of the problem, they will almost always execute much faster. In Shell Sort, for example, there are three nested loops. In the last iteration of the outer loop, the middle loop will execute N-1 times and the inner loop may (worst-case) execute O(N) times, but the worst-case time is far less than O(N^2).
-
leppyr64 wrote:
When you nest loops you multiply the complexity.
If the number of iterations on an inner loop is proportional to the size of the problem, and will be the same for all iterations of the outer loop, then the complexity of the outer loop is a factor of N greater than that of the inner loop. The same will be true if the number of iterations for the inner loop will be uniformly distributed over a range, the top of which is proportional to the size of the problem. There will be occasions, however, where nested loops aren't nearly as bad as they appear because, while the worst-case time of the inner loops is proportional to the size of the problem, they will almost always execute much faster. In Shell Sort, for example, there are three nested loops. In the last iteration of the outer loop, the middle loop will execute N-1 times and the inner loop may (worst-case) execute O(N) times, but the worst-case time is far less than O(N^2).
Hmmm, how about this nested loop?
main()
{
List<int[]> n = new List<int[]>();for(int i=0;i<n.count;i++)> { n\[i\]=new int\[100\]; for(int j=0;j<n\[i\].length;j++)> { for(int k=0;k<n\[i\].length;k++)> { } } }}
Will this still be O(N^3)? The two inner loops is not proportional to the size of the problem.
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.
-
Hmmm, how about this nested loop?
main()
{
List<int[]> n = new List<int[]>();for(int i=0;i<n.count;i++)> { n\[i\]=new int\[100\]; for(int j=0;j<n\[i\].length;j++)> { for(int k=0;k<n\[i\].length;k++)> { } } }}
Will this still be O(N^3)? The two inner loops is not proportional to the size of the problem.
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.
This is when you can start talking about O(N*M^2), where M is the "usual" size of an array stuffed in the list. In reality you'd probably have some idea about how many elements are put in the arrays. Say you were storing four integers in each array, and had hundreds of these arrays in the list, you would probably refer to it as O(N), as the M is fairly insignificant. If the arrays contained n.Length items, then it would be ^3... Big-O notation is a very rough analysis, you are generally interested in the highest power. Depends on data too, some sort algorithms are worst case O(N^2), but the likely case is much gentler.
Mark Churchill Director, Dunn & Churchill Pty Ltd Free Download: Diamond Binding: The simple, powerful, reliable, and effective data layer toolkit for Visual Studio.
Alpha release: Entanglar: Transparant multiplayer framework for .Net games. -
This is when you can start talking about O(N*M^2), where M is the "usual" size of an array stuffed in the list. In reality you'd probably have some idea about how many elements are put in the arrays. Say you were storing four integers in each array, and had hundreds of these arrays in the list, you would probably refer to it as O(N), as the M is fairly insignificant. If the arrays contained n.Length items, then it would be ^3... Big-O notation is a very rough analysis, you are generally interested in the highest power. Depends on data too, some sort algorithms are worst case O(N^2), but the likely case is much gentler.
Mark Churchill Director, Dunn & Churchill Pty Ltd Free Download: Diamond Binding: The simple, powerful, reliable, and effective data layer toolkit for Visual Studio.
Alpha release: Entanglar: Transparant multiplayer framework for .Net games.I see. So in the example above, if N>100, M (Integer in each array) does not really matter? But if N < M ,then it matters. So I can say that the best case is just O(N) and the worst is O(N^3)?
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, Given a pseudo code below:
main() { for(int i=0;i<n;i++)> { x[i]=func1(func2(x[i])); } } func1(x[]) { for(int i=0;i<length(x);i++)> //Do something here } func2(x[]) { for(int i=0;i<length(x);i++)> //Do something here }How can I compute for the Asymptotic notation? I know that the loop in main() is O(n) and both func1 and func2 are O(n). But How can I combine the 3? Can I even combine the 3 to get O(N^3)? or it will be just O(3N)? Thanks! :)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.
Hey Guys, don't want to start another thread so here it goes...
for(int i=0;i<n;i++)>
int x=1+1; //Constant Operationis this O(N) or O(1)? I'm just doing constant operation inside a loop.
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.
-
Hey Guys, don't want to start another thread so here it goes...
for(int i=0;i<n;i++)>
int x=1+1; //Constant Operationis this O(N) or O(1)? I'm just doing constant operation inside a loop.
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.
It is O(1). It has nothing to do with what is inside the loop (as long as it is not another loop dependent upon "n"), just how many times you execute the loop. In your stated case, it is linear, for each increase of n you only execute the loop one more time.
-
Hey Guys, don't want to start another thread so here it goes...
for(int i=0;i<n;i++)>
int x=1+1; //Constant Operationis this O(N) or O(1)? I'm just doing constant operation inside a loop.
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.
You are doing the constant operation N times...
Mark Churchill Director, Dunn & Churchill Pty Ltd Free Download: Diamond Binding: The simple, powerful, reliable, and effective data layer toolkit for Visual Studio.
Alpha release: Entanglar: Transparant multiplayer framework for .Net games. -
You are doing the constant operation N times...
Mark Churchill Director, Dunn & Churchill Pty Ltd Free Download: Diamond Binding: The simple, powerful, reliable, and effective data layer toolkit for Visual Studio.
Alpha release: Entanglar: Transparant multiplayer framework for .Net games.Yeah. But it doesn't matter right? Its still O(n). It doesn't matter if the operations inside the loop is a expensive or inexpensive operation?
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.
-
Yeah. But it doesn't matter right? Its still O(n). It doesn't matter if the operations inside the loop is a expensive or inexpensive operation?
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.
Yep, it doesnt matter if the execution time is trivial. The main thing is that if you double N then you double the execution time. N*10 -> 10*t, etc. In that exact case the compiler would probably optimise it to x = 2 ;)
Mark Churchill Director, Dunn & Churchill Pty Ltd Free Download: Diamond Binding: The simple, powerful, reliable, and effective data layer toolkit for Visual Studio.
Alpha release: Entanglar: Transparant multiplayer framework for .Net games. -
Good Day, Given a pseudo code below:
main() { for(int i=0;i<n;i++)> { x[i]=func1(func2(x[i])); } } func1(x[]) { for(int i=0;i<length(x);i++)> //Do something here } func2(x[]) { for(int i=0;i<length(x);i++)> //Do something here }How can I compute for the Asymptotic notation? I know that the loop in main() is O(n) and both func1 and func2 are O(n). But How can I combine the 3? Can I even combine the 3 to get O(N^3)? or it will be just O(3N)? Thanks! :)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.