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?
8
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.