5

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?

TonyZ
  • 123
  • 1
  • 8
  • 2
    You don't know the length of each individual list, but you know the total length of all lists, which is O(n^2). Also rather than printing each and every pair of pairs in each list I would rather just output the pairs in the list as they are all equal to each other. In this case the effort is clearly O(n^2). In the algorithm as stated (print all pairs of pairs) you need to know something about the max length of each list, otherwise the worst case (all n^2 pairs in one list) effort is indeed O(n^4). – Henry Jul 01 '17 at 10:24
  • So I guess the book is wrong then. They can't claim the algorithm is O(n^2) if they permutate each list. But your idea of use outputting each list is great! Thanks. – TonyZ Jul 02 '17 at 03:21
  • I'm not really good with algorithms so I'm not yet sure how to compute the exact runtime of lines 6 to 9 (in relation to previous lines). But I would like to point out that the N in lines 2 to 5 is _**different**_ from that in lines 6 to 9. – jflaga Jul 02 '18 at 05:07
  • 2
    I'm not sure what is written in that book but this problem can be solvable in O(n^2) time using Hashing data structure. – User_67128 Feb 10 '20 at 20:20

1 Answers1

0

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);
            }
        }
Ombuna Dante
  • 1
  • 1