CODEWITHSUNDEEP
javabig-o
Softey
Softey

Reputation: 1491

Big O Nested for Loop issue

 public static void main(String[] args) {
        int count = 0;
        int n = 20;
        for (int i = 0; i < n; i++) {
            for (int j = i; j > 0; j--) {
                count++;
            }
        }
        System.out.println(count);
    }

Above is the code of a simple nested for loop and me and my colleagues are having issues with what the Big O of this would be.

As I can see each for loop is o(n) and o(n)*o(n) makes o(n^2). There is however issue due to the fact that the second for loop takes it starter off i from the first loop and doesn't execute for example in the first loop when J is 0. I thought this wouldn't affect it as two sets of data n-i for the first loop and j-i for the second loop are still being traversed. Any clarity would be appreciated.

Upvotes: 2

Views: 129

Answers (3)

GreySage
GreySage

Reputation: 1180

The outer loop runs n times. For each iteration of the outer loop, the inner loop runs a different number of times, first 0, then 1, 2, ...n-1, n, which = Summation from 0 to n = n(n+1)/2 ~= n^2/2 which is O(n^2)

see http://en.wikipedia.org/wiki/1_%2B_2_%2B_3_%2B_4_%2B_%E2%8B%AF

Upvotes: 1

Zereges
Zereges

Reputation: 5209

Outer loop will run exactly n times, while inner loop is dependant on the value of i. But basically, it is doing 0, 1, ..., n-1 loops, which is total of (0 + n-1) * (n) / 2 = (n^2 - n) / 2 which is O(n^2)

Upvotes: 5

Lawrence Aiello
Lawrence Aiello

Reputation: 4658

Any time you have two nested loops, you must assume the absolute worst case (that is, the loop executes n times). So the big O notation here is O(n^2).

Upvotes: 1

Related Questions