How do you detect if an algorithm is running at O(nlogn)? Given only input and output(e.g. runtime), how do you know if an algorithm is running at O(nlogn) time complexity?  

For example, how does LeetCode detect my code is running at O(nlogn)？
https://leetcode.com/problems/sort-list/description/


  Sort a linked list in O(n log n) time using constant space complexity.




Here's what I think:

I assume the complexity formula looks like  $ f(x) = a\cdot x \cdot\log_{b} x\ $ 

Then for input $x_2 = 2x_1$, $ \frac{f(x_2)}{f(x_1)} = 2\cdot\log_{x_1}x_2 
$

So I take inputs like $2,4,8,16...$, get each runtime let's say $i_1,i_2,i_3,i_4... $. Then check if runtime ratio $\frac{i_2}{i_1}, \frac{i_3}{i_2} ,\frac{i_4}{i_3} \approx \log_{2}4, \log_{4}8,\log_{8}16...$. 

If it is, then I would "guess" it's running at O(nlogn).

Can I make a good "guess" based on the "characteristic" I described above?
I would like to apologize for sloppy notation in advance.

Recall that $\log_2 10^{10} &lt; 34$, so that for any practical purposes, $O(n \log n)$ will be bounded by $34 \cdot O(n)$, which of course is $O(n)$ (again for all practical purposes).

That means that if language A is 34 times faster than language B, then an $O(n)$ algorithm in B is indistinguishable from an $O(n \log n)$ algorithm in language A.

In practice, it's not possible without a theoretical analysis of the algorithm.

However, it's often simpler to distinguish an $O(n \log n)$ algorithm from an $O(n^2)$ algorithm (in the same language, at least), although we do have problems distinguishing an $O(n \log n)$ algorithm in Python from an efficient $O(n^2)$ in C/C++ in programming contests.