Yes, V8 has optimised string slicing to O(1). This does of course depend a lot on what else happens to all the strings, they might need to get copied later on.

The relevant implementation from the above link is:

// The Sliced String class describes strings that are substrings of another
// sequential string.  The motivation is to save time and memory when creating
// a substring.  A Sliced String is described as a pointer to the parent,
// the offset from the start of the parent string and the length.  Using
// a Sliced String therefore requires unpacking of the parent string and
// adding the offset to the start address.  A substring of a Sliced String
// are not nested since the double indirection is simplified when creating
// such a substring.
// Currently missing features are:
//  - handling externalized parent strings
//  - external strings as parent
//  - truncating sliced string to enable otherwise unneeded parent to be GC'ed.
class SlicedString: public String {
  // ...
};

Also beware of your quick test results. As you are doing nothing with the y variable, the slicing and even the whole loop might get eliminated as dead code by the optimiser. If you are doing benchmarks, do them on practical real world data.

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

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.

Well, the best way to get your answer is to just take 2 minutes and write a loop that does it both ways a thousand times and check firebug to see which one is faster ;)

I've had to optimize a lot of string munging while working on MXHR and in my experience, plain String methods are significantly faster than RegExps in current browsers. Use RegExps on the shortest Strings possible and do everything you possibly can with String methods.

For example, I use this little number in my current code:

var mime = mimeAndPayload.shift().split('Content-Type:', 2)[1].split(";", 1)[0].replace(' ', '');

It's ugly as hell, but believe it or not it's significantly faster than the equivalent RegExp under high load.

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.

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.