CODEWITHSUNDEEP
javaalgorithm
WillGates
WillGates

Reputation: 75

running time of 3 nested loops

I am quite confused on whether this alogrithm has a running time of O(n^2) or O(n^3). The program looks like this:

int count=0;

for (int i =0; i<n; i++){
    for (int j =i+1; j<n; j++){
        for (int k =j+1; k<n; k++){
            count++;
        }
    }
}

System.out.print("count: " + count);

I used an example of n=7. This gave me a result (count) of 35. I know that the i and j loops together has the running time of the gaussian sum, which is 1+2+3...n=O(n^2). I tried to figure out the full running time of all 3 loops by doing some calculations. I used the Gauss sum formula given by: enter image description here

I figured out that making gaussian sums and adding them up gives me the correct result.(starting from i=2 until i=n-1) The formula I got to was:

enter image description here

How would I remove the summation sign and get a regular "formula"?

Thank you for your time!

Upvotes: 0

Views: 2090

Answers (3)

Nelfeal
Nelfeal

Reputation: 13269

While Jeff Bowman's answer is correct, I feel like being able to come up with the exact formula is interesting and can be useful. The formula you got in the end is correct, but you mention that you want to "remove the summation sign", effectively simplifying the formula.
In the following, sum_{i=a}^{b}[y(i)] means the sum of y(i) for i from a to b.
Starting from your formula:

count = sum_{i=2}^{n-1}[(n-i)*(n-i+1) / 2]
2*count = sum_{i=2}^{n-1}[(n-i)*(n-i+1)]
2*count = sum_{i=2}^{n-1}[(n-i)^2 + (n-i)]
2*count = sum_{i=2}^{n-1}[(n-i)^2] + sum_{i=2}^{n-1}[(n-i)]
2*count = sum_{i=1}^{n-2}[i^2] + sum_{i=1}^{n-2}[i]
2*count = (n-2)(n-1)(2*(n-2)+1)/6 + (n-2)(n-1)/2
12*count = (n-2)(n-1)(2*n-4+1) + (n-2)(n-1)*3
count = (n-2)(n-1)(2*n)/12
count = (n-2)(n-1)(n)/6

You can clearly see that count is in O(n^3) but not in O(n^2).

Upvotes: 1

Jeff Bowman
Jeff Bowman

Reputation: 95704

From Wikipedia, emphasis mine:

Big O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity.

Consider what happens as n approaches infinity: You are taking the summation of n - 2 elements. As n approaches infinity, the -2 is going to become a uselessly small term, so you can ignore* it and multiply by n.

(* You're not properly ignoring it, but there exists a constant k such that your outer loop/summation will run fewer than kn times, which means that it still belongs to O(n).)

By similar logic, the expression you're summing belongs to O(n²), because despite the i, the term you're summing will be strictly less than kn² for some constant value of k. i may vary between 2 and n - 1, but that does not have any effect on how (n - i)((n - i) + 1) / 2 trends as n approaches infinity; it still grows less than kn² for some constant value of k, so the function is still in O(n²).

Because you're taking a summation of O(n) values of O(n²) order, your function is in O(n³) overall.

Upvotes: 1

Makoto
Makoto

Reputation: 106470

Big-Omega is a lower bound, so stating that your algorithm has a Ω(n2) is sufficient given that i, j and k are all running bound to some value of n.

Upvotes: 0

Related Questions