1

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;
}
Androme
  • 2,399
  • 4
  • 43
  • 82
  • 5
    Big-O notation always refers to worst case. – Turnor Sep 08 '10 at 15:32
  • 1
    @Turnor: Huh? Bachmann-Landau notation tells you how fast two functions grow in relation to each other. That's it. It doesn't tell you anything about what those functions *mean*. In programming, we generally use Bachmann-Landau notation to compare worst-case, best-case, average-case, amortized worst-case, almost-always-case space, time and step complexities. – Jörg W Mittag Sep 08 '10 at 17:11
  • You will have to be more specific. Big-O simply tells you whether one function grows faster than another function. But you don't tell us *which* function you are looking for. Space complexity? Time complexity? Step complexity? And which case are you looking for? Worst case, best case, average case, amortized worst case? And are you *sure* you want Big-O and not Big-Θ? At the moment, the question doesn't contain enough information to be answered. – Jörg W Mittag Sep 08 '10 at 17:14
  • @Jörg: Correct, but Big-O notation refers specifically to the upper bound, or the worst case scenario. There are different notations for the other behaviours, such as Big-Omega for the average case. – Turnor Sep 08 '10 at 17:20
  • 1
    @Turnor Big-O notation is also used for average case. Big-Omega, Big-Theta, Small-Omega, etc, can be used for any function. Best, worst or average. They say something about the upper bound, lower bound or upper and lower bound of the function. For example `Ω(n)` would mean that the worst case(or average case?) scenario is at least `n`. – Ishtar Sep 08 '10 at 17:42
  • @Turnor: Big-O does *not* refer to the worst case scenario. It doesn not refer to *any scenario at all*. It simply says whether one function grows faster than another function. What those functions *mean* is *completely* irrelevant. I would be *very* suprised if you could find any mention of the runtime of computer programs in Bachmann's paper from 1894. – Jörg W Mittag Sep 08 '10 at 17:49
  • I think you guys are trying to say the same thing different ways. The accepted answer at http://stackoverflow.com/questions/471199/what-is-the-difference-between-n-and-on basically says that to have `O(n²)` means your function will never grow at more than `n²` as `n` approaches infinity. So as R.Count grows bigger, there will never be a set of rectangle values (a "case") that will cause the function to grow at a rate of more than `n²`. The fact that certain rectangle values could potentially cause the function to run in constant time with relation to R.Count is irrelevant to Big-O notation. – StriplingWarrior Sep 08 '10 at 19:35
  • @StriplingWarrior, I don't think they are saying the same thing. While @Jörg is technically correct, the term "worst case" is often used when describing Big-O because you want to stop people thinking about best case. It's easy to think, "values entered in my log file are chronological, people are usually searching for one of the last few items therefore a reverse linear search will be O(1)". That's a best/average case based on **how** the search method is used in that scenario. It does not speak to the scalability of the underlying algorithm, which is usually what we want to talk about... – Kendrick Sep 09 '10 at 14:17

2 Answers2

3

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².

StriplingWarrior
  • 151,543
  • 27
  • 246
  • 315
1

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

Kendrick
  • 3,747
  • 1
  • 23
  • 41
  • Note, I'm assuming your i approaches n at the rate of 1 increment per nested loop. I don't see you modifying the value of i in that code anywhere, but I also can't find mayonaise in the refrigerator so I may have missed it... – Kendrick Sep 08 '10 at 15:44
  • 1
    O(1) is a trivial case (like item count on an object when that's a stored value) If you're processing all the elements, best case is O(n) – Kendrick Sep 08 '10 at 15:45
  • If you could hand-pick the first few rectangles to cause your two `if` statements to be true the first time through, then your function would not "grow" with relation to the number rectangles that are passed in. Therefore, the function is Big-Omega(1). – StriplingWarrior Sep 08 '10 at 19:42