# 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 say it’s running at O(nlogn).

Is my method right?

A test result of MergeSort based on array.