Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Big O for multi loops

Tags:

java

big-o

    count++;
    count++;
    count++;
    for (int i = 0; i < n; i++)
    {
        for(int j = 0; j < i*i; j++)
        {
            for (int k = 0; k < j; k++)
            {
                count++;
                sum++;
            }
        }
    }
    count++;
    return count;
}

Trying to get the Big O of this coding. Struggling to understand how the loops interact. When I run it, I get n = 25 count = 898960. I've tried O(n)^5+9 all the way to O(n)^5/n

All other examples of this problem don't deal with I is used in the second loop (I*I) and j is used in the third loop

like image 937
Novabomb Avatar asked Jan 28 '19 19:01

Novabomb


Video Answer


2 Answers

Almost always the best way to compute complexities of kinda loops should be done by making use of sigma notation.

enter image description here

P.S. I don't write necessary +1s in the formulas since it is not important for Big-O notation and doesn't affect max power which is 5.

like image 76
snr Avatar answered Nov 06 '22 09:11

snr


It looks like it is O(n^5).

for (int i = 0; i < n; i++) // 0 to n -> O(n)
    for(int j = 0; j < i*i; j++) // 0 to n * n -> O(n^2) repeated n times -> O(n^3)
        for (int k = 0; k < j; k++) // 0 to n * n -> O (n^2) repeated O(n^3) times -> O(n^5)

In the best case scenario, three nested loops would give you O(n^3), but as you have the second loop repeat (n^2) times, that will square its complexity and of the third loop as well. So in a simple mathematical notation that will be: (n) * (n * n) * (n * n) = n^5.

like image 40
Siavas Avatar answered Nov 06 '22 08:11

Siavas