Menu
I've got a question about calculating Big O running times for a series of loops, that are nested in an outer for loop.
For example:
for (50,000 times)
{
for (n times)
{
//Do something
}
for (n-2 times)
{
//Do something
}
for (n times)
{
//Do something
}
for (n-2 times)
{
//Do something
}
}
The outer loop is a constant, so I think that is ignored. Is it then as easy as doing the following calculation?
N + N-2 + N + N-2
2N + 2(N-2)
4N - 4
O(4N - 4)
O(4N) - after removing the -4 constant
Is this correct?
Thanks.
889
The outer loop executes N times. Every time the outer loop executes, the inner loop executes M times. As a result, the statements in the inner loop execute a total of N * M times. Thus, the complexity is O(N * M).
You can calculate big O like this: Any number of nested loops will add an additional power of 1 to n. So, if we have three nested loops, the big O would be O(n^3). For any number of loops, the big O is O(n^(number of loops)).
It will be 0(n^3) complexity as there are 3 loops with 0(n) complexity. As your number of loop increases, the time complexity of your method keeps on multiplying. So you have n loops in your program, then time complexity of your program will be 0(n^n).
The Time Complexity of a loop is considered as O(n) if the loop variables are incremented/decremented by a constant amount. For example following functions have O(n) time complexity.
This is O(n)
(you are only interested in what is the "largest" part of the equation, and you strip the constant).
If you had a loop i from 1..n and another loop inside j from i..n, it would be O(n^2).
143
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
