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, no registration required.

So I just took a data structure midterm today and I was asked to determine the run time, in Big O notation, of the following nested loop:

for (int i = 0; i < n-1; i++) {
    for(int j = 0; j < i; j++2) {
        //1 Statement
    }
}

I'm having trouble understanding the formula behind determining the run time. I thought that since the inner loop has 1 statement, and using the series equation of: (n * (n - 1)) / 2, I figured it to be: 1n * (n-1) / 2. Thus equaling (n^2 - 1) / 2. And so I generalized the runtime to be O(n^2 / 2). I'm not sure this is right though haha, was I supposed to divide my answer again by 2 since j is being upped in intervals of 2? Or is my answer completely off?

share|improve this question

closed as off topic by dasblinkenlight, kevin cline, gnat, Yusubov, Dynamic Oct 15 '12 at 19:11

Questions on Programmers Stack Exchange are expected to relate to software development within the scope defined by the community. Consider editing the question or leaving comments for improvement if you believe the question can be reworded to fit within the scope. Read more about reopening questions here.If this question can be reworded to fit the rules in the help center, please edit the question.

2  
Was that a j++2 or a ` j+=2`? –  dasblinkenlight Oct 11 '12 at 19:37
3  
When it comes to big O notation, you do not need to divide your answer by anything: all you need to do is to keep the highest power, and throw away everything else. The answer to this one is O(n^2) –  dasblinkenlight Oct 11 '12 at 19:39
    
@dasblinkenlight: can you clarify why this is (n^2)? It is a nested loop, but it seems that j is a constant, therefore, it would not be squared, but rather O(n). (not very familiar with this notation, so an explanation would be great). –  gahooa Oct 11 '12 at 19:41
    
j is not a constant. As n increases the inner loop takes proportionally more time. –  Philip Oct 11 '12 at 19:46
1  
Belongs on the theoretical computer science forum. –  kevin cline Oct 11 '12 at 20:06

1 Answer 1

To be precise, //1 statement would matter a lot in calculating the Big-O notation for a given piece of code. But considering that it takes a constant time ( I am supposing it is a count+=1 statement) then your solution would go like:

(Sigma i (over 1 to n) (Sigma j (over 1 to i))

And this would lead to O(n^2).

I suggest that you solve the problems at this link once. These will give you a good idea.

share|improve this answer

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