Big-O complexity of nested loops

Question

I'm confused about the complexity of the following (the operation performed inside the inner loop is in constant time):

Pseudocode:

for i = 1 to n
   for j = i to n
      for k = i to j
         x := x + 1;
      end for
   end for
end for;

Code:

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

O(n^3) ?

`question-mauvaise.c:4:3: unexpected token '???', did you mean '?'?` — , Mar 14 '13 at 21:44
Can you please format your code properly? And ideally translate it? — djechlin, Mar 14 '13 at 21:45
And honestly, you need to read http://whathaveyoutried.com. I can think of a dozen ideas here you might have to get started and don't think there is much honor in helping you avoid doing that. — djechlin, Mar 14 '13 at 21:47

score 1 · Answer 1 · answered Mar 14 '13 at 21:43

1

O(n^3) ???

Yes, even if you don't bother translating your homework from French.

answered Mar 14 '13 at 21:43

how i can get O(n^2) ? – user2151641 Mar 14 '13 at 21:52
@user2151641 By getting rid one of the loops? – Mar 14 '13 at 21:53
how i can calcule that with sigma ? – user2151641 Mar 14 '13 at 21:58
O( n * n * n) which is O (n^3). The cost is mutliplied cause it's nested. If they were side by side as opposed to nested it'd be O(3n) or O (n) cost. This is basic algorithms 101. – apollosoftware.org Mar 14 '13 at 22:00
Are you sure it is O(n^3)? The loops are not starting at 0, nor do all of them go to n? – Nashibukasan Mar 14 '13 at 22:01
1

@Nashibukasan ["There's a reason asymptotic complexity is called **asymptotic** and not **identical**..."](http://stackoverflow.com/questions/14305869/whats-the-complexity-of-for-i-for-o-i1/14305886#14305886) – Mar 14 '13 at 22:02
@H2CO3 Thanks! I was getting confused myself. – Nashibukasan Mar 14 '13 at 22:15

score 0 · Answer 2 · answered Mar 14 '13 at 21:44

0

It's the product of O(outer loop in outer loop control) * O(inner loop in inner loop control).

answered Mar 14 '13 at 21:44

djechlin

2 Answers2