Time/Space cost of Taxicab algorithm?

The following is an algorithm for generating "Taxicab numbers" using a priority queue (pq). Vector is an arbitrary data type that allows for storage of two number and their cubed sum. For those unaware (although you really don't need to know), a taxicab number is an integer that can be expressed as the sum of two cubes of integers in two different ways: $a^3+b^3 = c^3+d^3$. An example would be $1729 = 12^3 + 1^3 = 10^3 + 9^3$.

for i = 1..n
pq.insert( Vector(i^3+i^3,i,i) )

prev = Vector(0, 0, 0)

while not pq.empty()
curr = pq.deleteMin()
if prev == curr
print curr is a Taxicab number that can be expressed as
prev^3 + prev^3 and curr^3 + curr^3
prev = curr
if curr < N
j = curr + 1
pq.insert( Vector(curr^3 + j^3, curr, j) )

I know inserting an item into the priority queue is $O(\log n)$ but I am not sure how this relates to space usage and runtime. Can someone help?

• Have you looked at en.wikipedia.org/wiki/… ? Nov 11 '14 at 3:41
• @emab I am actually interested in the algorithm as a whole. Not sure if that is just the data structure though. Nov 11 '14 at 4:13
• Duplicate of our reference question?
– Raphael
Dec 11 '14 at 14:08

If you think about this program, you will realize pretty quickly that the vectors you're pushing onto the stack iterate over the values [a^3 + b^3, a, b] for all $1\leq a, b\leq N$ This means you're pushing $N^2$ items onto the stack over the course of the program.
Since each removal (and push, depending on the implementation of the PQ) takes $\Theta (\lg N)$ time, your algorithm would run in $\Theta (N^2\lg N)$ time. There's a straightforward $\Theta (N^2)$ solution, so you're not optimal yet.