Selecting best model based on linear, quadratic and cubic fit of data I have a Java code that performs a linear regression on a set of data using the Gauss-Jordan elimination. It calculates a linear, quadratic and cubic functions using the least squares method.
My problem is choosing a function out of the three that best models my data. This is ofcourse, without plotting the curve. So lets say I have a set of data {x:1,2,3,4} {y:3,8,910}, and I get a linear, quadratic and cubic function for it using the least squares method. 
How do I choose which function is the right model for my data? 
 A: Model selection will result in an estimate of the residual variance that is biased low.  This will bias all other aspects of inference and inflate $R^2$.  The unbiased estimate of $\sigma^2$ has in the denominator $n - p - 1$ where $p$ is the number of pre-specified parameters excluding the intercept.  It is not clear that model selection will help.  One can just use a regression spline with default knot locations (usually based on quantiles of the predictor distribution), choosing the number of knots based on what complexity the effective sample size will support.  The R rms package makes this easy, and course notes at http://biostat.mc.vanderbilt.edu/rms will help.  Removal of "non-significant" terms will hurt inference.  The use of AIC can sometimes backfire if the modeling is not highly structured.  I use AIC to tell me the optimum number $k$ of knots for a large number of predictors if I restrict each predictor to have $k$ knots.  This structure minimizes the damage caused by model uncertainty.
A: The general term for what you are asking about is model selection. You have a set of possible models, in this case something like
$$
\begin{aligned}
y&=\beta_0 + \beta_1x &\textrm{(linear)}\\
y&=\beta_0 + \beta_1x + \beta_2x^2 &\textrm{(quadratic)}\\
y&=\beta_0 + \beta_1x + \beta_2x^2 + \beta_3x^3  &\textrm{(cubic)}\\
\end{aligned}$$
and you want to determine which of these models is most parsimonious with your data. We generally worry about parsimony rather than best-fitting (i.e, highest $R^2$) since a complex model could "over-fit" the data. For example imagine your timing data is generated by a quadratic algorithm, but there's a little bit of noise in the timing (random paging by the OS, clock inaccuracy, cosmic rays, whatever). The quadratic model might still fit reasonably well, but it won't be perfect. However, we can find a (very high order) polynomial that goes through each and every data point. This model fits perfectly but will be terrible at making future predictions and, obviously, doesn't match the underlying phenomenon either. We want to balance model complexity with the model's explanatory power. How does one do this?
There are many options. I recently stumbled upon this review by Zucchini, which might be a good overview. One approach is to calculate something like the AIC (Akaike Information Criterion), which adjusts each model's likelihood to take the number of parameters into account. These are often relatively easy to compute. For example, AIC is:
$$ AIC = 2k -2ln(L) $$
where L is the likelihood of the data given the model and k is the number of parameters (e.g., 2 for linear, 3 for quadratic, etc). You compute this criterion for each model, then choose the model with the smallest AIC. Another approach is to use cross-validation (or something like that) to show that none of your models are over-fit. You could then select the best-fitting model.
That's sort of the general case. However, as @Michelle noted above, you probably don't want to be doing model selection at all if you know something about the underlying phenomenon. In this case, if you have the code or know the underlying algorithm, you should just trace through it to determine the algorithm's order. Gaussian elimination is an interesting case, as the "pat" answer, $O(N^3)$, isn't technically right. .
Also, keep in mind that the Big-O order of the algorithm isn't based on empircal observation: (i.e., the best-fit to the observed run time). It's more of a limiting property, taken as $N \rightarrow \infty$. Suppose your run-time were given by
$$t(N) = 0.0000001n^2 + 999999999n$$
I would bet that a runtime-vs-input size plot for that would be pretty linear-looking over the ranges you're likely to test, but the algorithm would technically be considered $O(n^2)$.
A: I'm not 100% sure but if the model is time to sort data you should probably include a $x\log(x)$ or something like this (perhaps its $x^2\log(x)$) as I think this term appears in theoretical time complexity calculations for sorting data.
