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
Performance
|complexity
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