1
$\begingroup$

I've implemented an algorithm, that when analyzed should be running with the time complexity of $O(n \log n)$.

However when plotting the computational time against the cardinality of the input set, it seems somewhat linear and computing $R^2$ confirms this somewhat. When then sanity checking myself by plotting $n$ on the $x$-axis and $n \log_2 n$ on the $y$-axis with python, and plotting this it also seemed linear. Computing $R^2$ (scipy.stats.linregress) further confuses me, as I get $R^2=0.9995811978450471$ when my $x$ and $y$ data is created as so:

for n in range(2, 10000000):
    x.append(n)
    y.append(n * math.log2(n))

Am I missing something fundamental? Am I using too few iterations for it to matter? When looking at the graph at http://bigocheatsheet.com/ it does not seem linear at all.

$\endgroup$
  • $\begingroup$ What exactly did you analyse? The worst-case behaviour of the algorithm? Also, note that $O$ denotes upper bounds, so a linear function is within $O(n\log n)$, did you mean that you derived a complexity of $\Theta(n\log n)$? $\endgroup$ – Discrete lizard Apr 25 at 6:13
  • $\begingroup$ Yes I analyzed the worst-case. And when running it, I fed it both random data, and data that would give me the most computations possible. While it's definitely slower when running on the second set of data, it's still linear. $\endgroup$ – VolatileEngine Apr 25 at 6:22
  • $\begingroup$ Remember that $\log n$ "is a small constant" for all $n$s you can run an $O( n \log n) $ algorithm on on your computer. $\endgroup$ – Pål GD Apr 25 at 6:26
  • $\begingroup$ Related question. Also, this answer applies. $\endgroup$ – Raphael Apr 25 at 6:32
  • $\begingroup$ It might be linear till some constant. $\endgroup$ – Mr. Sigma. Apr 25 at 6:32
1
$\begingroup$

Just some general observations.

  • O(n log n) is only an upper bound. If it's not tight, that's your explanation right there.
  • A Θ(n log n) running time can have many different components, for instance

    $\qquad\displaystyle a \cdot n\log n + b \cdot n \log \log n + c \cdot \sqrt n + d \cdot n + e \cdot \log n + d$

    While technically the linearithmic term dominates, if $a$ is small compared to the other coefficients you will have a hard time detecting it.

  • Measuring wall-clock running time is noisy without end, inparticular because the coefficients mentioned above get skewed by platform details. Try investigating counts, for instance of a dominant operation or block.
  • Linear regresssion always works. Since the "difference" between $n \log n$ and $n$ is rather small (also considering above point), it's not susprising you'd get a high confidence. Run linearithmic regression and compare!
$\endgroup$
  • $\begingroup$ Good point on suggesting to measure counts, or some other property that depends only on your algorithm and not on the implementation. $\endgroup$ – Discrete lizard Apr 25 at 6:54
  • $\begingroup$ @Discretelizard I think it's fair to count implementation specifics; my point was to remove the machine (metal, I/O, OS, competing tasks, ...) from the measurement. $\endgroup$ – Raphael Apr 25 at 8:07
  • $\begingroup$ Well, if you want to compare with the analysis of your algorithm, I'd say you should try to eliminate the rest. Measuring performance of implementations is a reasonable thing to do in general, but not necessarily what would be best here. $\endgroup$ – Discrete lizard Apr 25 at 8:12
  • $\begingroup$ @Discretelizard The OP will have to clarify what they want. Imho, if you want to compare (the performance of) your implementation to (the analysis of) the abstract algorithm -- to check against performance bugs, say, or validate the model you used for analysis -- then counting only those things that appaear identically in both implementation and algorithm is rather meaningless. $\endgroup$ – Raphael Apr 25 at 8:14
  • 1
    $\begingroup$ Yes, the OP should clarify that more. However, what I propose is not necessarily meaningless. There are many cases in which the theoretical analysis is/cannot be as tight or precise as you would expect the algorithm to behave for 'usual instances' (and where modelling these instances is also out of the question). For example, I recently implemented a distributed protocol for which the best theoretical result was a bound on the number of rounds 'with high probability'. These number of rounds is not an implementation detail. It is not a priori clear how such a bound behaves in practice. $\endgroup$ – Discrete lizard Apr 25 at 8:28

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.