How can I compute the Big-O notation for a given piece of code?

Posted by TheNew Rob Mullins on Programmers See other posts from Programmers or by TheNew Rob Mullins
Published on 2012-10-11T19:35:24Z Indexed on 2012/10/11 21:47 UTC
Read the original article Hit count: 206

Filed under:
|

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?

© Programmers or respective owner

Related posts about Performance

Related posts about complexity