Java Code Complexity

Question

int n=3;
int sum = 0;  
for (int i = 0; i < n; i++) {  
    for (int j = n - 1; j >= i; j = j - 2) {  
        sum = i + j;  
        System.out.println(sum);  
    }  
}

i've been trying to find the complexity of this code (O(?) etc)
any ideas?

`O(n2)` .. you need to understand Big O, it can be even said `O(n3)` or `O(n4)`. — vidit, Oct 20 '13 at 19:19
@pajton [Homework tag is now deprecated](http://meta.stackexchange.com/questions/147100/the-homework-tag-is-now-officially-deprecated) — vidit, Oct 20 '13 at 19:20
i'm sortta lost inside the nested loop is it a sequence or something? — user2900830, Oct 20 '13 at 19:21
Read [A puzzle related to nested loops](http://stackoverflow.com/questions/13621550/a-puzzle-related-to-nested-loops/13622284#13622284) To get some idea how to solve it. — Grijesh Chauhan, Oct 20 '13 at 19:21
@vidit ah, I didn't know! I am returning to SO after quite of break:) — pajton, Oct 20 '13 at 19:22
Maybe this will help a little: [Plain English explanation of Big O](http://stackoverflow.com/q/487258/1393766). — Pshemo, Oct 20 '13 at 19:27
@pajton Actually, [the homework tag is now officially depricated](http://meta.stackexchange.com/questions/147100/the-homework-tag-is-now-officially-deprecated). — AJMansfield, Oct 20 '13 at 19:40

score 1 · Accepted Answer · edited Oct 21 '13 at 07:57

1

I'll explain just to clear my own understanding. The first loop run n times. Now, let's discuss the inner loop.

First iteration, it will run from n-1 to 0 inclusive, with increments of 2, resulting in n/2 iterations. Second Iteration, it will run from n-1 to 1 inclusive, with increments of 2, resulting in (n-1)/2 iterations. And so on, the last iteration will be from n-1 to n-1 inclusive, and it will be 1 iteration.

Counting all iterations, it will be [n/2 + (n-1)/2 + .... 1] ≈ n²

edited Oct 21 '13 at 07:57

Grijesh Chauhan

57,103
20
141
208

answered Oct 20 '13 at 19:38

vidit

6,293
3
32
50

I think you mean `n^2` but not `n2` ? – Grijesh Chauhan Oct 21 '13 at 05:16
@GrijeshChauhan- Yes sir, please feel free to edit it. – vidit Oct 21 '13 at 06:05

score 0 · Answer 2 · answered Oct 20 '13 at 19:23

Well, constant, for the fixed n... :-) But if you want a complexity in n, it's O(n^2) - it would be o(n^2) if the inner cycle went from n to 0, but as it is, we only reduce the time in half by ending at i (imagine a square; the area where j >= i is a triangle), and by another half by stepping j by 2, which together is just a constant multiplicative factor 1/4 (IOW not changing the asymptotic complexity).

Java Code Complexity

2 Answers2