# 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[0] == curr[0]
print curr[0] is a Taxicab number that can be expressed as
prev[1]^3 + prev[2]^3 and curr[1]^3 + curr[2]^3
prev = curr
if curr[2] < N
j = curr[2] + 1
pq.insert( Vector(curr[1]^3 + j^3, curr[1], 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?

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.