Menu
I have searched a bit on StackOverflow and have understood the complexity up to the point of the j-loop, which is O(n2). However with the nested addition of the k-loop, I am confused as why the complexity becomes O(n3). Can someone help me understand this?
From my understanding, the i-loop have n iterations and the j-loop have 1+2+3+...+n iterations n*(n+1)/2 which is O(n2).
for(i = 1; i < n; i++) {
for(j = i+1; j <= n; j++) {
for(k = i; k <= j; k++) {
// Do something here...
}
}
}
EDIT: Thanks for all your help guys :) Balthazar, I have written a piece of code to which will increment counters depending on which loop they are in, kinda a crude way of step-by-step:
#include <iostream>
int main(int argc, const char * argv[])
{
int n = 9;
int index_I = 0;
int index_J = 0;
int index_K = 0;
for (int i = 1; i < n; i++) {
for (int j = i+1; j <= n; j++) {
for (int k = i; k <= j; k++) {
index_K++;
}
index_J++;
}
index_I++;
}
std::cout << index_I << std::endl;
std::cout << index_J << std::endl;
std::cout << index_K << std::endl;
return 0;
}
I ran this code from n=2 to n=9 with increments of 1 and have got the following sequence:
From the counters, it can therefore be seen that:
i = n-1 giving the complexity of O(n) and j = ((n-1)*n)/2 giving the complexity O(n2). A pattern for K was hard to spot but it is known that K depends on J, therefore:
k = ((n+4)/3)*j = (n*(n-1)*(n+4))/6 giving a complexity of O(n3)
I hope this will help people in the future.
EDIT2: thanks Dukeling for the formatting :) Also found a mistake in the last line, corrected now
417
As the nested loops always run to completion and there is a constant amount of code within the inner loop, the time complexity can be determined by taking the sum of the number of inner loop iterations in the worst case.
A for loop can have more than one loop nested in it A for loop can have more than one loop nested in it.
The time Complexity of a loop is considered as O(Logn) if the loop variables are divided/multiplied by a constant amount. And also for recursive calls in the recursive function, the Time Complexity is considered as O(Logn).
In a common special case where the stopping condition of the inner loop is j < N instead of j < M (i.e., the inner loop also executes N times), the total complexity for the two loops is O(N2).
the k-loop has O(j-i) complexity
the j-loop has O((n-i)*(n-i)) complexity
the i-loop has O(n*n*n)=O(n^3) complexity
anyway, you know that it is not O(n^2) because the first two loops are O(n^2) and it is not more than O(n^3) because there are only 3 loops
99
If you're accustomed to Sigma Notation, here is a formal way to deduce the time complexity of your algorithm (the plain nested loops, precisely):
NB: the formula simplifications might contain errors. If you detect anything, please let me know.
35
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
