How can I compute the Big-O notation for a given piece of code?
- by TheNew Rob Mullins
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?