Worst case should be O(n) (copying all n-1 elements to new array).

A linked list would be O(1) for a single deletion.

For those interested I've made this lazily-crafted benchmark. (Please don't run on Windows XP/Vista). As you can see from this though, it looks fairly constant (i.e. O(1)), so who knows what they're doing behind the scenes to make this crazy-fast. Note that regardless, the actual splice is VERY fast.

Rerunning an extended benchmark directly in the V8 shell that suggest O(n). Note though that you need huge array sizes to get a runtime that's likely to affect your code. This should be expected as if you look at the V8 code it uses memmove to create the new array.

1. Using copy on write, the copy can be avoided in some cases right up to the point where the data mutated. AFAIK, not many languages expose or even use COW. I've mostly only ever seen it referenced in OS design for things like process forking.

2. Academics say to always use a linked list. However, practically, Array lists are almost always preferred. The problem with linked lists is that they are not cache friendly. In the worst case, your CPU has to go out and hit main memory for every single node accessed (millions of cycles per node!).

In contrast Array lists keep all the nodes in a contiguous block of memory. CPUs, when they access memory, will pull in a block of memory into cache. For traversal of an array, the cost can easily be in the 10s of cylces per element.

Further, the cost of adding to an array list isn't as bad as you might think. These lists will often overallocate so they can avoid copying over the data when you hit the end of the array.

And in practice, middle or beginning insertion just isn't all that common. You almost always do tail insertions with lists and very often you don't do any deletions at all!

So how do you index a linked list, so that deletion is ACTUALLY constant time?

You iterate and delete/split at the same time. You still have n time, but you don't end up with 2*n time. That is pretty much the case for a linked list, when you want to frequently go through the list and remove, split, or merge the list at various points based on the current element. Again, in practice this happens almost never.

also, is a language's implementation, like JS, of an array ever a linked list?

Depends. In fact, in javascript it could easily start out as a linked list and later be transformed into an array list based on jit optimizations.

The ECMA specification does not specify a bounding complexity, however, you can derive one from the specification's algorithms.

push is O(1), however, in practice it will encounter an O(N) copy costs at engine defined boundaries as the slot array needs to be reallocated. These boundaries are typically logarithmic.

pop is O(1) with a similar caveat to push but the O(N) copy is rarely encountered as it is often folded into garbage collection (e.g. a copying collector could only copy the used part of an array).

shift is at worst O(N) however it can, in specially cases, be implemented as O(1) at the cost of slowing down indexing so your mileage may vary.

slice is O(N) where N is end - start. Not a tremendous amount of optimization opportunity here without significantly slowing down writes to both arrays.

splice is, worst case, O(N). There are array storage techniques that divide N by a constant but they significantly slow down indexing. If an engine uses such techniques you might notice unusually slow operations as it switches between storage techniques triggered by access pattern changes.

One you didn't mention, is sort. It is, in the average case, O(N log N). However, depending on the algorithm chosen by the engine, you could get O(N^2) in some cases. For example, if the engine uses QuickSort (even with an late out to InsertionSort), it has well-known N^2 cases. This could be a source of DoS for your application. If this is a concern either limit the size of the arrays you sort (maybe merging the sub-arrays) or bail-out to HeapSort.

Array#splice is O(n) because it can shift up to each array element per call. See: What's the time complexity of array.splice in Google Chrome?

In determining the time complexity of an algorithm, as long as each O(n) operation is in series and the number of O(n) operations is a constant factor (which are the case here), it's still O(n). O(n²) is the consequence of nested loops; that is, for each n we perform another O(n) operation.

This code uses only two sequential calls to Array#splice along with an O(n) spread for a total of O(3n) which is equivalent to O(n).

"My runtime was slower" -- Time complexity and runtime are totally distinct things. Much of runtime rests on implementation details, fixed overhead expenses (constant factors) that are ignored by big O, how large LC's test cases are, the composition of the test cases, inaccuracies LC's test case measurement, etc. Use a benchmark under your own control on very large random inputs to be more certain. Two O(n) codes rarely exhibit identical performance characteristics--time complexity is only concerned with the rate of growth of an algorithm.

As for this particular comparison, keep in mind that builtin functions are highly optimized. I'm assuming this runs in NodeJS (V8), so many builtins are written in C++ (or Torque) (and V8 is not unique in this).

Implementing builtins natively at a lower-level means the memory is likely to be compact and regular so cache accesses benefit from locality, less pointer chasing, opportunities for stack allocation, etc. for loops in high-level code are harder to optimize. They involve index variables, performing comparisons, branching and so forth, all of which needs to be effectively translated to bytecode in a way that may be sub-optimal. In cases when the builtin implementation is in JS, the designers have done much work to make them as efficient as possible.

In Array#splice's case, it's written in Torque which is translated to efficient assembly.

In your code, let a = Array.from({length:nums.length}). Incurs allocation overhead for two objects.

In short: benchmark fairly, don't conflate complexity and speed, and use builtins whenever possible (use a profiler to determine rare cases when not to).

Normally a question like this is quite difficult to give a definite answer to, because different implementations of Javascript have different time complexities for basic array operations (such as creating a new array of size n). Javascript arrays will typically be implemented either as dynamic arrays or hashtables, and these data structures have different performance characteristics.

So, there is no definitive time complexity for splice to remove one element from an array. What we can say is that removing one element takes linear time for a dynamic array, and as @Ry- points out in the comments, also linear time for a hashtable, because of the need to renumber the later indices. We can also say that it's highly likely one of these two data structures is used, and no sensible implementation will take more than linear time to do splice.

Either way, the worst case for your algorithm is when x = 'aa...aa' and y = 'abb...bb', i.e. x is n copies of 'a', and y is 'a' followed by (m - 1) copies of 'b'.

For a dynamic array or a hashtable, then the time complexity for just the splice operations is O(nm²). This is because the outer loop iterates O(nm) times (note the i-- inside the loop, which happens every time the letter 'b' needs to be removed), and the splice operation requires shifting or renumbering O(m) elements in yArr after index i.

But suppose some more exotic data structure is used which supports removing an element in sub-linear time (e.g. a skip list). In that case, the above only gives O(nm) times the complexity of the "remove" operation. But we haven't counted concat yet; this creates a new data structure and copies every item into it, which will still take linear time. concat is called O(n) times and takes an average of O(n + m) time per call, so the complexity of just the concat operations is O(n² + nm).

So the time complexity is very likely O(n² + nm²), and certainly at least O(n² + nm); not linear.

The space complexity is O(n), since the length of yArr is never more than twice as long as xArr.

You might consider whether you want to use an object instead; all JavaScript objects (including Array instances) are (highly-optimized) sets of key/value pairs with an optional prototype An implementation should (note I don't say "does") have a reasonable performance hashing algorithm. (Update: That was in 2010. Here in 2018, objects are highly optimized on all significant JavaScript engines.)

Aside from that, the performance of splice is going to vary a lot between implementations (e.g., vendors). This is one reason why "don't optimize prematurely" is even more appropriate advice for JavaScript applications that will run in multiple vendor implementations (web apps, for instance) than it is even for normal programming. Keep your code well modularized and address performance issues if and when they occur.

(V8 developer here.)

Array.prototype.slice is O(n), where n is the number of elements in the slice.
String.prototype.slice is O(1), thanks to our implementation of SlicedStrings, which are just storing pointer, offset, length to the original string and avoid copying the characters (except when they're tiny, so that copying a handful of characters is actually cheaper and smaller than storing a reference; that's still O(1)).

The key difference is that strings are immutable, and arrays are not. When you do str1 = "Hello World"; str2 = str1.slice(2, 5);, since there is no way to modify str1's contents afterwards, str2 doesn't need to ensure that it's unaffected by any such modification.
When you do a = [1, 2, 3, 4]; b = a.slice(1, 3); a[1] = "changed"; console.log(b[0]);, then you expect to see 2, not "changed". That's why b has to be an actual copy. (In theory, a copy-on-write approach would be possible, but V8 doesn't do that for array slices.)

"Shallow copy" means that nested objects will not be copied. Example:

let nested = {property: "value"};
var a = [nested];
var b = a.slice(0, 1);
a[0].property = "new value";
console.log(a === b);          // false, `b` is a copy
console.log(a[0] === b[0]);    // true, `nested` was not copied
console.log(b[0] === nested);  // true
console.log(b[0].property);    // "new value"