How do you detect if an algorithm is running at O(nlogn)?

Question

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?

Answer 1

Look at the definition of f(n) = O (g (n)): There is a constant c > 0, and N > 0, such that for every n > N we have f (n) ≤ c * g (n).

If you run your problem with sizes up to size X, then we can pick N = X + 1, and all your measurements up to size X are completely irrelevant. So you can only determine the time complexity of an algorithm by mathematical analysis, not by measurements.

You can of course measure the execution time of a specific implementation for various problem sizes, and then say for example "for various problem sizes n from 1 to $10^{15}$ where I measured the execution time, 3.74 n $log_2$ n microseconds was a good approximation to the execution time of this algorithm".

Answer 2

I would like to apologize for sloppy notation in advance.

Recall that $\log_2 10^{10} < 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.