1
$\begingroup$

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.

N (points) vs Steps taken by radix sort

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.