Hacker News new | ask | show | jobs
by HenriTEL 889 days ago
pop() would have been a much better example, as ruby providing delete_at is a mistake IMO, since it runs in O(n), chances are that you're using the wrong data structure. Go providing append but not pop is inexplicable
2 comments

There are many, many situations where delete_at is a completely reasonable operation. It may be O(n) but it is a blazing fast O(n) as it is just a memmove. For example if you are writing a TODO app and you want to delete a task it is likely a very acceptable solution. You would need millions of tasks before you couldn't remove it withing a few milliseconds. Most other solutions even though they have better time complexity would be slower in practice. (But benchmarks would be needed to verify this).

I would say that the biggest concern with delete_at is if you are using it inside another O(n) loop, then it becomes O(n^2) which does scale up fast enough to become a performance issue.

There is nothing wrong with O(n). It can be faster than O(1) depending on the size of n and what you're doing (small arrays are usually faster than hashmaps for example).

Big-O just tells you how something scales. It doesn't really tell you how fast something is.