The number of representation can be as big as $\sqrt{n},$ so this is a lower bound on the complexity of any algorithm. Now, the algorithm is to iterate through all $k\leq \sqrt{n},$ and try to represent $n-k^2$ as a sum of squares (in all possible ways). This is equivalent to factoring, so the complexity will be not that bad above optimal (factoring is "hard", but not so hard compared to $\sqrt{n}.$

The number of representation can be as big as $\sqrt{n},$ so this is a lower bound on the complexity of any algorithm. Now, the algorithm is to iterate through all $k\leq \sqrt{n},$ and try to represent $n-k^2$ as a sum of squares (in all possible ways). This is equivalent to factoring, so the complexity will be not that bad above optimal (factoring is "hard", but not so hard compared to $\sqrt{n},$ indeed, this algorithm runs in time $O(n^{1/2 + \epsilon})$ for any $\epsilon > 0.$)