News for hackers. Stuff that matters.
Re:Big-O Algorithm Complexity Cheat Sheet by gizmo686 on Saturday May 04, 2013 @12:21PM (#5655323)
If we are talking about the same thing (an array that you reallocate to twice its size when you fill), then it has an amortized O(1) time to append something to the end. If you want to insert something in the beggining, you will need to move n elements down an index. A random location will average n/2, which is O(n)
Re:Big-O Algorithm Complexity Cheat Sheet by alecbenzer on Saturday May 04, 2013 @01:02PM (#5655463)
Ah, true. I guess the chart should probably distinguish between arbitrary index insertion and appending.
Re:Big-O Algorithm Complexity Cheat Sheet by dllthomas on Saturday May 04, 2013 @01:31PM (#5655578)
Though with a gap buffer, you can have O(1) to insert/delete at some other point. Costs O(n) to move that point, though.