0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ If you have given only input and output then, it will be impossible to know the asymptotic complexity of the algorithm. $\endgroup$ – aaag Dec 31 '18 at 9:38
  • 1
    $\begingroup$ I'm pretty sure that LeetCode just has tests with a fixed time limit, like most automated competitive programming judges. They do not attempt to test for the asymptotic runtime, but simply indicate the asymptotic complexity of an algorithm with a fast enough implementation. However, it seems that your actual question is whether your method to statistically estimate asymptotic complexity works. If so, please clarify that in your question. $\endgroup$ – Discrete lizard Dec 31 '18 at 9:59
  • $\begingroup$ @Discretelizard Thank you firstly. Hmmm. I think I am dong the wrong thing.. Mathematically, I can't use a property to prove what it is. I mean, the Unnecessary and sufficient condition sort of thing. But based on the "method", the "characteristic" I described in the question, at least I can make a good "guess", right? $\endgroup$ – Rick Dec 31 '18 at 15:42
1
$\begingroup$

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".

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you :). I think I am dong the wrong thing.. (I did not analyze the code coz I just can't. So I was trying to seek some solutions from the output characteristic). Mathematically, I can't use a property to prove what it is. I mean, the Unnecessary and sufficient condition sort of thing. But based on the "method", the "characteristic" I described in the question, at least I can make a good "guess", right? $\endgroup$ – Rick Dec 31 '18 at 15:46

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.