CODEWITHSUNDEEP
javatime-complexity
Ankita Agrawal
Ankita Agrawal

Reputation: 113

Big O Time Complexity of Nested Loop with recursion

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

Upvotes: 1

Views: 239

Answers (2)

CryptoFool
CryptoFool

Reputation: 23079

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.

Upvotes: 2

Todd Caywood
Todd Caywood

Reputation: 49

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.

Upvotes: 0

Related Questions