current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free.
up vote 1 down vote favorite

I have loops like this:

for(int i = 0; i < n; i++) {
    for(int j = 0; j < i; j++) {
        sum += 1;
    }
}

It's O(n * ), but I'm not sure what the j < i loop is.

I have some tests that I ran,

n = 10, runs = 45

n = 20, runs = 190

n = 40, runs = 780

n = 80, runs = 3160

n = 10, runs = 12720

It seems to be converging onto .5*n^2, but I'm not quite sure.

share|improve this question
5  
On CS.SE: Big O: Nested For Loop With Dependence says its O(n^2). –  MichaelT Jan 13 '14 at 3:29

4 Answers 4

up vote 14 down vote

You are summing up the numbers from 1 to n, incrementing the value by one each time. This is essentially the classic Gauss sumation which is:

sum(1 .. n) = (n * n-1)/2

This also happens to be the number of times through the loop.

(n^2 - n) / 2
(n^2)/2 - n/2

When representing Big O, only term with the highest power is used and constants are thrown away, and thus the answer is O(n2).

More about this particular problem can be read on CS.SE at Big O: Nested For Loop With Dependence

share|improve this answer
    
Well, he is summing the numbers from 1 to n-1, but yes, the concept and everything else is correct. –  Benjamin Brumfield Jan 22 '14 at 14:15
up vote 0 down vote

if i==0 then j ranges from 0 to -1 ==> (not possible) 0 if i==1 then j ranges from 0 to 0 ==> 1 if i==2 ,, ,, ,, 1 ==> 2 . . . if i==n-1 then j from 0 to n-2 ==> n-1 iterations

summing them

It is S = 0 + 1 + 2 + 3 +.......+ n-2 + n-1 same as S = n-1 + n-2 + ...... + 1 + 0

summing 2*S= (n-1) + (n-1) +.............(n-1) //n times

==> 2*S = (n-1)*n ==> S= (n-1)*n/2

share|improve this answer
up vote 0 down vote

On the 1st iteration of the outer loop (i = 0), the inner loop will iterate 0 times On the 2nd iteration of the outer loop (i = 1), the inner loop will iterate 1 time On the 3rd iteration of the outer loop (i = 2), the inner loop will iterate 2 times
.
.
On the FINAL iteration of the outer loop (i = n ‐ 1), the inner loop will iterate n ‐ 1 times

So, the total number of times the statements in the inner loop will be executed will be equal to the sum of the integers from 1 to n ‐ 1, which is:

((n ‐ 1)*n) / 2 = (n^2)/2 ‐ n/2 = O(n^2) times
share|improve this answer
up vote -2 down vote

You can see that it follows a particular equation which is (n*(n-1))/2. e,g for n=5, runs=(n*(n-1))/2=5*4/2=10.So it is O(n*(n-1))=O(n^n-n)=O(n^2)[As in case of Big-O, lower order terms and constants are ignored]

share|improve this answer

protected by gnat Apr 27 at 6:33

Thank you for your interest in this question. Because it has attracted low-quality answers, posting an answer now requires 10 reputation on this site.

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.