Wow. (Update: I guess you are thinking of C arrays not Perl arrays, or at least an implementation much more like a naive, dynamic C array than what Perl actually uses.)
I'll agree with pop and shift being O(1) and not just in an average case. They are always O(1). (I won't argue with whether O() notation implies worst case or average case or whatever, mostly because I don't care.)
I'll agree with splice being O(N). Splicing to remove from the middle is always O(N/2). Splicing at position J elements from either end if often O(J). But splicing to insert K elements can be O(N+K). So averaging out to O(N) isn't a bad summary. Continuing to ignore some predicted objections to misuse of O(), I'd say splicing to remove is O(N/2) while splicing to insert is O(N+K). :)
If you push N times, then that is O(2*N), O(N) for the realloc() calls that likely end up copying the elements each time the array size doubles and O(N) for the N items being pushed. So push is O(2) on average. And using push on an array that both shrinks and grows is closer to O(1) than O(2) (yes, I'm still ignoring it).
If you unshift N times, then that is a bit more complex. I don't have swapped in the exact algorithm that is used for "leave some space at the front in case they unshift again", but I think it is also exponential (or is that "geometric"?) so unshift probably averages to O(3).
See Shift, Pop, Unshift and Push with Impunity! for another take on this.
- tye
In reply to Re^5: Array VS Linked List (O)
by tye
in thread Array VS Linked List
by asset
| For: | Use: | ||
| & | & | ||
| < | < | ||
| > | > | ||
| [ | [ | ||
| ] | ] |