Big O of unknown algorithm

Question

I got an unknown algorithm that I need to calculate the time complexity for (Big O). The only thing that I know about the algorithm is how long it takes to finish its calculations for a given number of values. Just to make it clear, the algorithm is taking a number and returning the time taken when using that number.

Using the time taken and the numbers given for that time, I get a nearly straight line if I make a plot of the time taken against the numbers given. The line fits well to the complexity of O(n log n). The problem is still that even if the line does fit, I can't prove that the complexity really is n log n. so How can I prove the complexity?

Here are some values:

time: 0.008  number of elements: 4000
time: 0.100  number of elements: 40000
time: 0.1200 number of elements: 400000
time: 1.4000 number of elements: 4000000

Answer 1

The comments are right: you can't prove the complexity, and you need more points to model it empirically. This is shown by the plot of your current data.

If you get more data, one thing you could do to investigate it is a log-log plot, plotting the log of time t against the log of number of elements n. This gives you a straight line with gradient p if your relationship is of the form: t = n^p, as illustrated below with some simulated data. The black points are for a y=x^2 relationship, the green for y=x, and the red for y=x*log(x) is somewhere inbetween.

If you think it's an nlogn relationship, you could simply plot t against nlogn, and you should get a straight line. Regression analysis is certainly possible, but if you look at your current data, you actually get a very good straight line fit from a linear regression (shown on the first plot above), and I certainly wouldn't say that it's linear on that basis.