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?