2

In a team project we need to remove the first element of an array, thus I called Array.prototype.shift(). Now a guy saw Why is pop faster than shift?, thus suggested to first reverse the array, pop, and reverse again, with Array.prototype.pop() and Array.prototype.reverse().

Intiutively this will be slower (?), since my approach takes O(n) I think, while the other needs O(n), plus O(n). Of course in asymptotic notation this will be the same. However notice the verb I used, think!

Of course I could write some, use jsPerf and benchmark, but this takes time (in contrast with deciding via the time complexity signs (e.g. a O(n3) vs O(n) algorithm).

However, convincing someone when using my opinion is much harder than pointing him to the Standard (if it refered to complexity).

So how to find the Time Complexity of these methods?

For example in C++ std::reverse() clearly states:

Complexity

Linear in half the distance between first and last: Swaps elements.

gsamaras
  • 71,951
  • 46
  • 188
  • 305
  • 1
    *Why the Standard doesn't refer to the complexity of these methods* - Do you expect the readers to go through the spec and find out *why* the spec doesn't mention that? Or, are you directly asking about the complexity of those methods? Also, (I'm not sure), could the complexity depend on the implementation? i.e. could it be different across browsers? Does spec leave that *flexibility*? – Nisarg Shah Sep 26 '17 at 08:19
  • 1
    @gsamaras I think your hidden question is actually "where can I find the complexity of these methods documented?" Knowing why it isn't documented is useless :) – Peter Morris Sep 26 '17 at 08:24
  • 2
    AFAIK, The Standard doesn't mandate how these methods should be implemented. Also, JS is an interpreted language, so things like JIT and GC may start playing a role depending on array sizes and how often the code is called. In other words: benchmarking is probably your only option to get an idea on how different JS engines perform. – robertklep Sep 26 '17 at 08:27
  • @robertklep your comment should be an answer then. Nisarg well check the comment of robertklep, this could be an answer, so it's not that broad! Thanks! – gsamaras Sep 26 '17 at 08:30
  • Obligatory comment about premature optimization. I am assuming you are asking this question because you have narrowed down a killer performance problem in your app to this call to `shift`? Please also note that "complexity" is NOT necessarily related, at all, to performance. BTW, I guess you mean `reverse`. –  Sep 26 '17 at 09:40
  • Thanks @torazaburo, updated! You are so right about premature optimization, but my question was meant to be more generic (see the edit history). – gsamaras Sep 26 '17 at 09:46
  • As you yourself said, there is no such thing in complexity theory as `O(n) + O(n)`, or `2 O(n)`. From a complexity standpoint, `k O(n)` is identical to `O(n)`. `O(n log n)` is more complex than `O(n)`, but might well be faster, or faster most of the time. You should avoid confusing yourself and everyone else and stop talking about complexity, and just ask about "performance", which is something entirely different. –  Sep 26 '17 at 09:50

2 Answers2

2

how to find the Time Complexity of these methods?

You cannot find them in the Standard.

ECMAScript is a Standard for scripting languages. JavaScript is such a language.

The ECMA specification does not specify a bounding complexity. Every JavaScript engine is free to implement its own functionality, as long as it is compatible with the Standard.

As a result, you have to benchmark with jsPerf, or even look at the souce code of a specific JavaScript Engine, if you would like.

Or, as robertklep's comment mentioned:

"The Standard doesn't mandate how these methods should be implemented. Also, JS is an interpreted language, so things like JIT and GC may start playing a role depending on array sizes and how often the code is called. In other words: benchmarking is probably your only option to get an idea on how different JS engines perform".

There are further evidence for this claim ([0], [1], [2]).

gsamaras
  • 71,951
  • 46
  • 188
  • 305
1

An undisputable method is to do a comparative benchmark (provided you do it correctly and the other party is not bad faith). Don't care about theoretical complexities.

Otherwise you will spend a hard time convincing someone who doesn't see the obvious: a shift moves every element once, while two reversals move it twice.

By the way, a shift is optimal, as every element has to move at least once. And if properly implemented as a memmov, it is very fast (while a single reversal cannot be as fast).

  • @gsamaras: just between us, I found the idea of the double reversal to "benefit" from the fast pop (which is in fact a no-op) pretty naive. –  Sep 26 '17 at 09:47