Is this algorithm of O(n^4) avoidable?

Question

DISCLAIMER: This is not a homework question. I don't even go to school.

#include <stdio.h>
void printIntersect(float, float, float, float);

int main(){
   int x, y, z, a;
   float slopes[] = {5, 9, 4/3.0f, 2/3.0f, 3};
   float inter[] = {3, 2, 1, 0, 5/3.0f};  

   for(x = 0; x < (sizeof(slopes) / sizeof(slopes[0])) - 1; x++)
       for(y = 1; y < (sizeof(slopes) / sizeof(slopes[0])); y++)
           for(z = 0; z < sizeof(inter) / sizeof(inter[0]); z++)
                  for(a = 0; a < sizeof(inter) / sizeof(inter[0]); a++)
                      if(slopes[x] != slopes[y])
                          printIntersect(slopes[x], slopes[y], inter[z], inter[a]);

   return 0;
}

void printIntersect(float m_one, float m_two, float b_one, float b_two){
    float m_final, b_final, x_intersect;

    m_final = m_one - m_two;
    b_final = b_two - b_one;

    if(m_final < 0 && b_final < 0)
        m_final *= -1.0f, b_final *= -1.0f;

    if (b_final != 0)
        x_intersect = b_final / m_final;
    else
        x_intersect = 0;  

        printf("The intersection of y = %.2fx %c %.2f and y = %.2fx %c %.2f is x = %.2f\n",
            m_one, (b_one < 0) ? '-' : '+', b_one, m_two, (b_two < 0) ? '-' : '+', b_two, x_intersect);


    return;
}

Scenario: There was an exercise in one of my C books that I'm unsure of. What I got out of the question was that I was to have two arrays: one representing the possible slopes of a line, the other representing all possible y intercepts. The goal was to use all possible combinations of slopes and intercepts with two lines to find their intersection. I was to ignore parallel lines and duplicate lines (which is implicitly ignored anyway considering if they can't be parallel, then there's no way that they can be the same line).

Assuming that's premise (and I really don't care at this point, it's just an exercise), the program I wrote uses 4 nested for loops. You can see why that concerns me, but then again, maybe the 4 of them are necessary.

Since I can't have parallel lines, I iterate the slopes by starting with that of the first line and then iterate through all other slopes in the array as the second line's slope. It's this way that I get all possible combinations of slopes.

Intercepts are different because I can have a lines of the same intercepts and still have them be different. So iteration between those doesn't need to account for duplicates. That being said, the way I iterate through the array of intercepts should account for every possible pair in those two lines.

If the lines are not parallel, I call a function which will print the x intercept.

My question is, could this O(n^4) solution been avoided or at least simplified? Do you have any tips on processing arrays like these?

Answer 1

Given a slopes and b intersects, you can make a*b lines. There are a*b choose 2 pairs of lines. This is about half as much as a*b*a*b (it is (a*b*(a*b-1)/2). Given no additional information, it seems like you have to check all of them - so yep your algo is indeed O(a*a*b*b).

EDIT: Let's look at the question differently, in terms of the answer. Given a slopes and b intersects, and making a*b lines by combining them, how many intersections will we have? Let's assume for simplicity that the set of slopes is distinct.

This is a different question than asking how many intersects we have given n lines, because of the way the lines are constructed. Given one slope, we create b parallel lines. Given the next, we create another b parallel lines, none of which are parallel to the first set of lines. Repeat a times.

Within one set, we have no intersections since they're all parallel.

Between two sets, how many intersections do we have? None of the lines in one set are parallel to the lines in the other set, so each line in one set will intersect once with each line of the second set. As each set has b lines, there will be b*b intersections between any two sets.

Here we note that all these sets of lines also share the same set of b intersects. So, for each additional set of lines you intersect with the current set of intersected lines, you will add (b*b - b)*c = b*c*(b-1) intersections where c is the number of sets of lines already included, because the intersections at the b y-intercepts are already accounted for, so we only add b*(b - 1) intersections for each set of lines already there.

So we have our initial b^2 for two sets, plus b*(b - 1)*2 for adding the third, plus b*(b - 1)*3 for adding the fourth, etc., up to b*(b-1)*(a-1) for adding the ath set. That is, the number of intersections I is:

I = b^2 + 2b(b-1) + 3b(b-1) + ... + (a-1)b(b-1)

We can re-write b^2 as b + b(b-1):

I = b + b(b-1) + 2b(b-1) + ... + (a-1)b(b-1)

Factor out the common b(b-1) in the last a-1 terms:

I = b + b(b-1)[1 + 2 + ... + (a-1)]

We note that the sum of numbers from 1 to x is x*(x+1)/2:

                (a-1)*a 
I = b + b(b-1)  ------- 
                   2

        a*(a-1)*b*(b-1)
  = b + ---------------
               2

        (a^2 - a)(b^2 - b)
  = b + ------------------
                2

    a^2*b^2 - a^2*b - a*b^2 + a*b + 2b
  = ----------------------------------
                    2

Thus, whatever algorithm you use, you're going to have to generate that many separate pieces of output, which is indeed less than a^2*b^2, but not by a significant amount.