Given a data set of arbitrary size, what algorithm would be appropriate for performing the polynomial regression on the data set such that the highest degree of the polynomial is n? If there are multiple of such algorithms, what is more efficient for particular data sets (other then the obvious line fitting the data set according to its shape--or not)?
If you have decided in advance to allow polynomials with degree at most n, then "regression on the data set" amounts to finding a best-fit polynomial with that restriction. Avoid "over-fitting" the data set, by choosing a degree n higher than is justified by the extent and quality of data points.
The most common approach is a least-squares fit, minimizing the sum of squares of errors at the data points. The solution is found by solving a linear system of equations for the polynomial coefficients. Line-fitting (where one independent variable is present) entails solving a system of two equations for the slope and intercept (constant term).
Two other methods are minimizing the sum of absolute errors and minimizing the maximum absolute error (at any data point). These methods have solutions that can be obtained by linear programming algorithms.
Each of these methods has a variation in which relative errors (proportions of nonzero data) rather than absolute errors are used. More generally nonnegative weights may be assigned a priori to the data points in order to represent higher confidence in some data points (measurements) than in others.
The choice of method should be based on the quality of the data (how much variance do the errors exhibit) and on the time constraints for finding a solution. Since the solution is an approximation to data containing errors, the pursuit of a highly accurate solution to the approximation problem may quickly turn into a diminishing returns effort.