Solving a^3 + b^4 = c^3 + d^3 best runtime

user_8180838 0
Viewed 1331

Note: this question is different from Write all solutions for a^3 + b^3 = c^3 + d^3 because I need help understanding the runtime of the algorithm, not what the algorithm is.

In Cracking the Coding Interview, 6th Edition, pg. 69, there is the following example:

Print all positive integer solutions to the equation a^3 + b^3 = c^3 + d^3, where a, b, c, d are ints between 0 and 1000.

Here's the given optimal solution:

1 n = 1000
2 for c from 1 to n:
3     for d from 1 to n:
4        result = c^3 + d^3
5        append(c, d) to list at value map[result]
6 for each result, list in map:
7    for each pair1 in list:
8        for each pair2 in list:
9            print pair1, pair2

The book claims that the runtime is O(n^2).

However, I'm not sure how to put a bound on complexity of lines 6-9. I see that lines 6-7 loop through n^2 numbers, but I do not see how last for-loop on line 8 can be constant time for the overall runtime is O(n^2).

In fact, I can't come up with a bound for line 8 at all, because it depends on the length of each list, which I can only say is less than n^2, making the whole thing O(n^4).

Could someone enlighten me?

complexity-theory time-complexity algorithm
1 Answers

My solution in c#

 var hash = new Hashtable();
        for (int i = 1; i <= n; i++)
        {
            for (int j = i + 1; j <= n; j++)
            {
                var value = Math.Pow(i, 3) + Math.Pow(j, 3);
                if (hash.Contains(value))
                    Console.WriteLine(string.Format("{0},{1},{2}", hash[value], i, j));
                else hash.Add(value, i + "," + j);
            }
        }
user_46309690
Related