computer science - Complexity of the following algorithm to generate TaxiCab numbers? -

computer science - Complexity of the following algorithm to generate TaxiCab numbers? -

following algorithm generating taxicab numbers using priority queue(pq). vector arbitrary info type allows storage of 2 number , cubed sum. unaware(although don't need know), taxicab number integer can expressed sum of 2 cubes of integers in 2 different ways: a^3+b^3 = c^3+d^3. illustration 1729 = 12^3 + 1^3 = 10^3 + 9^3

for = 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] taxicab number can expressed prev[1]^3 + prev[2]^3 , 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 item priority queue o(log n) not sure how relate space , time complexity. can help ?

it's no worst o(n^2 log n), though might possible give tighter bounds it.

this block of code:

if curr[2] < n j = curr[2] + 1 pq.insert( vector(curr[1]^3 + j^3, curr[1], j) )

makes code equivalent, more efficient than:

possibles = empty list = 1..n j in i+1..n possibles.append( vector(i^3 + j^3, i, j) ) sort(possible_numbers) = 1..n prev = possibles[i] curr = possibles[i + 1] if prev[0] == curr[0] print curr[0] taxicab number can expressed prev[1]^3 + prev[2]^3 , curr[1]^3 + curr[2]^3

the size of possibles list o(n^2), making sorting o(n^2 log(n)). sec loop o(n) makes code o(n^2 log n).

algorithm computer-science time-complexity