31–40 of 46 posts
Earlier quoted context omitted.
Yes, but total time is never going to be less than total space, when expressed in big-O notation
Why couldn’t it?
Heavily simplified due to caches etc. To the point where people sometimes measure in cache misses instead as that is usually what actually matters.
Earlier quoted context omitted.
Why couldn’t it?
Because it takes n time to access n units of memory. Heavily simplified due to caches etc. To the point where people sometimes measure in cache misses instead as that is usually what actually matters.
Earlier quoted context omitted.
Fun bonus: they can be interchangeable, e.g. increasing space to reduce time.
Yes, but total time is never going to be less than total space, when expressed in big-O notation
For example, an in-place algorithm like Bubble Sort would have a O(1) space complexity, because it requires no extra memory (and 0 memory is a constant). Merge sort on the other hand is O(n) because it always uses additional memory for its intermediate stages, and that additional memory scales with n.
Doing a quick google, the first few sites I find seem to use a similar understanding https://www.geeksforgeeks.org/time-and-space-complexity-anal...
Earlier quoted context omitted.
Because it takes n time to access n units of memory. Heavily simplified due to caches etc. To the point where people sometimes measure in cache misses instead as that is usually what actually matters.
What if you allocate a huge chunk of memory and only use a small part of it? For example, checking if a list of numbers contains duplicates using a boolean array.
And if your implementation of an algorithm allocates more space in the big-oh sense than it can actually touch (eg. O(n) space for O(log n) time or whatever), that's just a wasteful implementation. Doesn't make the algorithm itself require more space than it has time to actually use.
Ah yes, the most reliable solution to a wrong choice of a data structure: add data-specific hacks until it works. For the life of me I can't figure out why people never consider replacing linked lists. Even without worst-case O(n) insertion, they usually behave worse than vectors, deques, or hives.
What is a hive in the context of data structures?
Perhaps a simple way to look at it is that it's like a dynamic array, but when the capacity is exceeded, you don't reallocate the array, just just allocate a new (exponentially larger) chunk and keep the old one as-is. Then just link the chunks in a (very short) linked list, or keep a separate small list of chunks (you're never gonna need more than 48, so you can just have a fixed allocation for it), or what have you. The bonus here is that it reduces latency on pushing and has more predictable performance.
Earlier quoted context omitted.
Yes, very common. You've seen "time complexity"; it's very common to talk about "space complexity" as well.
Fun bonus: they can be interchangeable, e.g. increasing space to reduce time.
Why was the solution not to get rid of the linked list and replace it with a red/black tree?
I got the impression that the expected performance of the double linked list insertion is actually O(1), since in most cases the elements arrive in sorted order. It's been a time since my algorithm courses, but I think all the 'normal' trees have log(n) insertion in that case.
Earlier quoted context omitted.
Yes, but total time is never going to be less than total space, when expressed in big-O notation
I’m not sure this definition of Big-O for space complexity is universal. When I’ve seen/used it, the size of the initial data wasn’t relevant, it was more about the additional memory required for the algorithm. For example, an in-place algorithm like Bubble Sort would have a O(1) space complexity, because it requires no extra memory (and 0 memory is a constant). Merge sort on the other hand is O(n) because it always…
space complexity is O(n) but auxiliary space complexity uses Theta for notation instead.
But people aren't too picky on the notation and usually say something like "O(1) extra space" instead of using theta.
Earlier quoted context omitted.
I got the impression that the expected performance of the double linked list insertion is actually O(1), since in most cases the elements arrive in sorted order. It's been a time since my algorithm courses, but I think all the 'normal' trees have log(n) insertion in that case.
O(n) is generally indistinguishable from O(log n) so if there is any chance of different behavior than the expected optimum, go with the better algorithm.
Earlier quoted context omitted.
I’m not sure this definition of Big-O for space complexity is universal. When I’ve seen/used it, the size of the initial data wasn’t relevant, it was more about the additional memory required for the algorithm. For example, an in-place algorithm like Bubble Sort would have a O(1) space complexity, because it requires no extra memory (and 0 memory is a constant). Merge sort on the other hand is O(n) because it always…
The confusion is around space complexity vs auxiliary space complexity (extra space). space complexity is O(n) but auxiliary space complexity uses Theta for notation instead. But people aren't too picky on the notation and usually say something like "O(1) extra space" instead of using theta. https://en.m.wikipedia.org/wiki/Space_complexity
Saying something is O(n) tells you it grows at most linearly, but this would also admit e.g. log n.
Saying something is Theta(n) tells you it grows exactly linearly: that is, it is not a slower growth rate like log n, nor a faster growth rate like n^2.