# Represent polynomial time complexity as linearythmic

To determine the experimental time complexity of radix sort, I wrote a program that counted the number of steps the algorithm took to sort N points. I ran that program for multiple N length arrays, and I plotted the steps taken in Excel. Then, using the trend line tool, I calculated the polynomial that best fit the function.

It gave me something along the line : $$Steps = 16n^{1.0932}$$

This seems to be $$O(n)$$, but my prof is telling us to represent this as $$O(n \log n)$$ . How would I go about to demonstrate this.

Thanks.

PS: If anyone is interested, here are my results.

You cannot "demonstrate" that a running time is $$\Theta(n\log n)$$ experimentally. All you can do is give evidence. Such evidence would be a constant $$C$$ such that for large $$n$$, $$Cn\log n$$ is a good approximation to the empirical running time.
You found the best polynomial approximation to your input. Since $$Cn\log n$$ is not a polynomial, this kind of approach cannot possibly give you the answer $$Cn\log n$$. If you want $$Cn\log n$$ to be a possible answer, you need to include such functions in the family of functions you are optimizing over.
Finally, to demonstrate that $$Cn\log n$$ is a better approximation that your polynomial approximation or a linear approximation, all you have to do is to compare the error in the approximation $$Cn\log n$$ to the errors in the other two options. Smallest error wins.