What should be the time complexity of below code snippet
void doSomething(int n) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
doSomeOtherStuff(n);
doSomething(n - 1);
}
}
}
void doSomeOtherStuff(int n) {
for (int i = 0; i < n; i++) {
//did some other stuff
}
}
Is the complexity calculation as: n^2(n + n^2) = O(n^4) is correct? If not please explain
Per my comments to the first answer, I think the complexity of this algorithm is much worse than O(n^4). @ToddCaywood actually first wrote what I was thinking in my head. This algorithm is actually something like:
O(n^(n^2))
an impossibly bad result. For large datasets, this thing is going to go off into space and never come back.
The way I first looked at this is that each level of recursion adds another set of NESTED for loops. For n==10, you have 20 nested for loops. It just keeps getting deeper and deeper as n grows.
Yes, O(n^4) is correct.
doSomeOtherStuff(n) is obviously complexity O(n), done n times, also done n times, so the inside portion is O(n^3).
Keeping this in mind, complexity of doSomething(n) [let's call that T(n)] = O(n^3) + T(n-1) where T(n-1) = O(n^3) + T(n-2), etc. Expanding to (n-1)(O(n^3)) + O(n^3) = n(O(n^3)) = O(n^4).
If you need a formal proof, you can follow the logic above pretty easily, expanded where needed.
n due to the recursion? Isn't it the number of nested loops that determines the 4 in this case? So since there are more than 4 nested loops, isn't this much worse than O(n^4)?