Verifying that measured time does fit O(n^3) I'm dealing with a homework.
We were given a software, with inputs, that we should measure and then verify that the time complexity is O(n^3).
I measured the software, picked best times from each batch (since that's the least affected one), and ended up with this:
304   70000
574   480000
775   1190000
850   1580000
1070  3130000
1557  9740000
1965  19540000

Now I'm really lost. I know how to calculate a model using least squares, but I have no idea how to do that for O(n^3). Plus I don't know how I would verify that the model is correct.
 A: The easiest way is to get cubic root of this data and see if the transformed data shows linear dependence; seems so:

If you want to do this the right way, use nonlinear fitting tool like nls in R to fit $b \text{time}^a$:
> nls(V2~b*V1^a,data=s,start=list(b=1,a=3))
Nonlinear regression model
  model:  V2 ~ b * V1^a 
   data:  s 
       b        a 
0.002525 3.002639 
 residual sum-of-squares: 1.036e+09

Number of iterations to convergence: 4 
Achieved convergence tolerance: 1.658e-07 

summary method will show you significance of parameters;
> summary(nls(V2~b*V1^a,data=s,start=list(b=1,a=3)))

Formula: V2 ~ b * V1^a

Parameters:
   Estimate Std. Error t value Pr(>|t|)    
b 2.525e-03  8.605e-05   29.35 8.61e-07 ***
a 3.003e+00  4.531e-03  662.64 1.49e-13 ***
---
Signif. codes:  0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1 

Residual standard error: 14400 on 5 degrees of freedom

Number of iterations to convergence: 4 
Achieved convergence tolerance: 1.658e-07 

it shows $O(n^3)$ hypothesis is highly supported.
