1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.