Big O for code snippet

Question

Hello it has been some time sins i have used Big O notation, so i'm a bit rusty.

I know that having 1 loop, that loops n times is O(n), and having 1 loop that loops n time within another loop that loops n times is O(n^2).

But in the following code snippet do i have a loop that loops n times, and within that a loop that loops n-i times.

What will the Worst and Best O notation be for this code?

The worst is where it runs without finding a collision, and the best will be when there are a collission between the 2 first rectangles.

class TestClass
{
    bool Run(List<Rectangle> R)
    {
        var b = false;
        var i = 0;
        var n = R.Count;
        var j = 0;
        while ((i < n-1 ) && !b )
        {
            j = i + 1;
            while (j<n && !b)
            {
                if ((R[i].x >= R[j].x - R[i].w) && (R[i].x <= R[j].x + R[j].w))
                    if ((R[i].y <= R[j].y + R[i].h) && (R[i].y >= R[j].y - R[j].h))
                        b = true;
                j++;
            }
            i++;
        }

        return b;
    }
}

public class Rectangle
{
    public int x;
    public int y;
    public int w;
    public int h;
}

Answer 1

As a commenter pointed out, Big-O is always about the worst case scenario, so if increasing the value of R.Count would tend to make your worst-case scenarios increase at a rate greater than n*log(n), you're getting into the realm of n².

Since you have a double-nested while loop, and no additional method calls, at a glance I'd have said it's O(n²).

However, in this case, since i and j never increment, and n never decrements, and your loops are both based on i or j being less than n, this function will either exit right away (based on your if statements), or it never will.

O(infinity)?

Edit

Okay, now that you increment them, the n*(n-i) bit basically averages out to n*(n/2) each time you run it (not an average of all runs, but rather an average for each run). This is because you'll be doing (n, n-1, n-2, ..., 3, 2, 1) inner loops as you move through the outer loop. If you fold this set in on itself, you can easily sum up the number of loops:

n + 1 == n + 1
(n-1) + 2 == n + 1
(n-2) + 3 == n + 1
...

So you end up with n/2 instances of n + 1, which comes out to (n² + n)/2. From a big-O standpoint, this is the same as n².

Answer 2

Your actual worst case running time is n X n/2 = n²/2. Throw away the constants, and it's O(n²)