Getting amortised O(1) prepend is interesting because it's just like append, except you "center" or "right-justify" (if you don't care about O(1) append) the array in the allocated space, and exponentially reallocate when full as with append.
Prepending would be O(1) because it's creating a new array instead of prepending in place. Still bugs me (seems inelegant, even if not necessarily inefficient) so I wrote my own version: https://news.ycombinator.com/item?id=18988075#18998572
>No, you still need to copy the old array to the new array.
That's just a lock (nontrivial but O(1)) and a memcpy (technically O(n) but trivial, and O(1) for the common case if it's implemented with vector instructions), plus in any event the sums-of-neighbors method has to be at least O(n) on an idealized Von Neumann machine because it must read every element of the source array and also write every element of the destination.
"Technically" O(n) is the only O(n). There isn't some widespread colloquial use of Big O notation where O(n) means something else. Whether it's trivial is beside the point, but for a large n, O(n) in both time and space can be prohibitive, and it may become important that I don't use such an algorithm. For example, if I have 8 GB of data and 12 GB of working memory I can't satisfy those space requirements.
> and O(1) for the common case if it's implemented with vector instructions)
What is the common case in your view? memcpy in the general case is O(n). That you can perform multiple copies in parallel might affect the real time, but it doesn't affect the time complexity because O(kn) = O(n) for a constant k even if that k = 1/16 or however many copies you can perform at once.
> plus in any event the sums-of-neighbors method has to be at least O(n) on an idealized Von Neumann machine because it must read every element of the source array and also write every element of the destination.
In idealized algorithmic analysis, but not necessarily real life. "Amortized O(1)," which I assume you concede is a commonly-used, meaningful and legitimate term, means "technically" an idealized O(>1) but O(1) in practice.
Calling memcpy inside a Ruby method call is amortized O(1) because for any "n" that fits within available memory, it will always be much faster than the other things in a Ruby method call, which involve dozens of locks, hash table lookups with string keys, dynamic type checks, additional Ruby method calls and so forth.
Likewise, computational complexity on an idealized Von Neumann machine isn't always the same on a real computer, in both directions. Dynamic allocations are theoretically O(n) but may be O(1) if the program never exceeds the preallocated space. Or suppose there were a loop over an array of pointers which dereferenced each pointer; the dereferences are theoretically O(1) but may be O(n) if they evict the parent array from the cache.
> What is the common case in your view?
Such as an array small enough that it can be copied with 10 or fewer vector load/stores.
> O(3n) = O(2n) = O(n)
Yes, that's my point. It's impossible to implement the example in less than idealized O(n) time, so O(n) and O(1) operations are equivalent complexity-wise WRT the entire method.
> In idealized algorithmic analysis, but not necessarily real life.
Big O notation is used for idealized algorithmic analysis. If you want to talk about real life, you can count cycles, seconds, watts etc.
> "Amortized O(1)," which I assume you concede is a commonly-used, meaningful and legitimate term, means "technically" an idealized O(>1) but O(1) in practice.
Yes, but I wouldn't take O(1) on its own to imply amortized complexity. Not that pretending that an array copy is O(1) in practice is particularly useful here since if you measure a copy operation in practice, you'll find that the time it takes scales roughly linearly with the size of the array. Not to mention that the space complexity is O(n) no matter how you put it.
> Such as an array small enough that it can be copied with 10 or fewer vector load/stores.
Are other cases conversely "uncommon"? My point here is that this is entirely your opinion and doesn't pertain to whether an array copy is O(1) or O(n) complex.
> Yes, that's my point. It's impossible to implement the example in less than idealized O(n) time, so O(n) and O(1) operations are equivalent complexity-wise WRT the entire method.
The one where you yourself even say it's O(n)? Big-O is concerned with asymptotic complexity. It's O(n) until you show us it's not (e.g. implementation code, not musings.)
Here's my second reply to him, where I myself point out that idealized Von Neumann machines don't exist in real life, and certain idealized O(n) operations (such as memcpy) may in real life for any possible "n" be cheaper than some baseline constant C (such as the cost of a Ruby method call): https://news.ycombinator.com/item?id=18988075#19001585
