CODEWITHSUNDEEP
javabig-o
malteser
malteser

Reputation: 485

Big-O of Triple Nested Loop

What would the Time complexity (Big-O) of such an algorithm be

for (int i = 1; i < n; i++) {
    for (int j = 1; j < i; j++) {
        for (int k = 1; k < j; k++) {
            x++;
        }
    } 
}

Is it exponential?

Assuming the input is n

Thanks!

Upvotes: 0

Views: 5615

Answers (3)

freddiev4
freddiev4

Reputation: 2621

for (int i = 1; i < n; i++) { // O(n) time complexity
    for (int j = 1; j < i; j++) { // O(n) time complexity
        for (int k = 1; k < j; k++) { // O(n) time complexity
            x++;
        }
    } 
}

The first loop does n number of computations. Your second loop continues to go until i reaches its condition, which is n, and k continues until jreaches its condition. Each loop is reaching the same condition, n

So, each loop has a time complexity of O(n); because they are nested, you multiply each n, which results in a total time complexity of O(n^3)

Upvotes: 7

salmanbw
salmanbw

Reputation: 1311

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). You can refer to this http://www.programmerinterview.com/index.php/data-structures/big-o-notation/ for more reference.

Upvotes: 0

Jean Logeart
Jean Logeart

Reputation: 53869

Each loop is O(n) so the overall is O(n^3)

Upvotes: 0

Related Questions