CODEWITHSUNDEEP
javascriptarraysalgorithmperformancetime-complexity
gsamaras
gsamaras

Reputation: 73444

Complexity of Array methods

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.

Upvotes: 2

Views: 1030

Answers (2)

user1196549
user1196549

Reputation:

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

Upvotes: 1

gsamaras
gsamaras

Reputation: 73444

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]).

Upvotes: 2

Related Questions