CODEWITHSUNDEEP
javaalgorithmfor-loopbig-onested-loops
Increase
Increase

Reputation: 19

Big O Notation of Java Nested Loops

I am aware of the various rates of Big O such as O(n^2) and O(n), and have no problem determining the Big O value of simple nested for loops such as the following.

for (int i = 0; i < n; i++)
    for(int j = 0; j < n; j++)
   //Simple Statement

The following loop is clearly O(n^2), but how does one go about solving for Big O when the inner nested loop is dependent on the outer loop. Example

for ( int i = 0; i < n; i++)
    for (int j = n - 1; j >= i; j--)
    //Simple Statement

would T(n) simply be n*(n-1-i) ?

Thanks in advance for the help!

Upvotes: 1

Views: 894

Answers (2)

ivern
ivern

Reputation: 141

The inner loop runs n + (n-1) + (n-2) + ... + 2 + 1 times. This is a Gaussian sum and equals n * (n + 1) / 2, or (n^2 + n) / 2, hence O(n^2).

Upvotes: 2

chasep255
chasep255

Reputation: 12185

It is still on the order of n^2. You only care about the most significant term. The second expression would look something line O(n^2 - an) where a is some sort of coefficient. All you really care about is the n^2.

Upvotes: 3

Related Questions