This post is optional reading, but is interesting, and helped DeriveIt's creators view data structures more clearly.
As you've learned about the different data structures, you've probably picked up on the idea that some data structures are slower than others. For example, Arrays and LinkedLists take more time to read/delete than Sets in some cases. Why is this the case?
Well, the slower data structures store more information! There's maintenance cost to upkeeping that extra information that they store.
In the case of an ordered data structure (like an Array or LinkedList), where elements have an index between 0 and N, if we add or delete an element at index i, we must shift over N - i + 1 elements to maintain the indexes properly. That gives us an O(n) cost to maintain ordered (indexed) data structures.
For Arrays, LinkedLists, and any other indexed data structures: This actually turns out to be a false bound - the true value is O(\log n), explained below - but this is the general illustrative idea. *
We have a choice of when we do the maintenance! We can do it right when we edit the data structure, like in the case of the array where we shift everything over immediately. For the array, time_read=O(1) yet time_write=O(n). Or, we can do it right when we read from the data structure, like with the LinkedList, where time_read=O(n) (we walk along the LinkedList, effectively reconstructing the index lazily) yet time_write=O(1).
The point is that we eventually need to do an O(n) operation if we edit an indexed data structure. It doesn't matter if it's an Array, or a LinkedList, or some other creative indexed data structure we invented. If we want to store "indexed" information, that's a fundamental cost we must face!
There is a formula that describes this idea: time_read+time_write=Maintenance Cost. This is a lot like a conservation of energy equation, and it holds for every data structure.
In general, the maintenance cost is determined by the information you want to store. It equals it equals the number of affectancies (items you might affect by making a change). It can often be computed before you even know what your data structure looks like! This is a powerful statement because it lets you make a sweeping statement about entire classes of data structures.
Now we're ready to talk about other data structures. Let's start with Sets, which are easy. For Sets and other unordered data structures, elements have no effect on each other the way they did in an Array (due to the index invariant). This means:
For Sets, HashMaps, and any other completely unordered data structures:
Finally, the last major data structure is a "sorted" or "ranked" data structure. This sits in-between an Array and a Set; it cannot be arbitrarily ordered like an Array, but is also not disordered like a Set. The sorting lower bound for n items is O(nlogn), which means the maintenance cost of one item is on aggregate logn.
Worth mentioning as a side-note that Maintenance Cost≥nbuild_time.
For BSTs, B-Trees, Sorted Arrays, and any other sorted data structures:
These are simply lower bounds. They are like speed limits; they are the best you can do, but of course, you can do worse than them. For example, a Sorted Array has O(n) insert time despite O(logn) being its lower bound maintenance cost.
Now we're going to break down many different data structures into classes, based on the information they store. We'll go into more depth than above, introducing subclasses like Stacks and Queues (simply lumped into ordered above). We'll do aggregate analysis in cases where the results are unaffected (wrapping all equations in a big O instead of using exact values).
Each new type of information will be written with an inline code block like type.
Note that data structures can always be combined at the cost of taking the larger of the two Maintenance Cost values. (eg if you store elements in both an Array and a Set for fast value lookups).
i = ability to look up any index.
Surprisingly, this is logn, (it's not n). Although, you can usually think of it as n, since the logn case is very rare, and comes with extra overhead.
BST:
You can store all your items in a self-balancing BST, where each node knows the number of nodes below it (this is called an "order statistic tree"). The position is the index, and it has the logn behavior of a BST. However, this is relatively rare.
O(logn) read i
O(logn) write i
Array:
O(1) read i
O(n) write i
LinkedList:
O(n) read i
O(n) write i
O(1) write i once we read i
Lazy Array Thought experiment where we don't actually perform any of the writes until the user reads to get the write cost to O(1). w = # of additions since last read. * :
O(n⋅w) read i We can actually get this to O(n + w \log w) by sorting the changes by index and iterating through them backwards, and if we use Counting sort then we can get this down to O(n + w). Either way, the O(n) cost survives, which is what we're trying to show here. *
O(1) write i
1i = ability to look up a single index, like the last element.
Stack:
O(1) read i=n
O(1) write i=n
Queue (Doubly Linked):
O(1) read i=0,n
O(1) write i=0,n
Specific Index Array A data structure where we can only look up, add, and remove at a specific fixed index (or n if there aren't enough elements yet), like i=7 or generally i=L. * :
O(1) read i=L
O(1) write i=L
v = ability to look up a single value.
Set:
O(1) read v
O(1) write v
HashMap:
O(1) read v
O(1) write v
k = ability to look up any kth smallest/largest element.
BST:
O(logn) read k
O(logn) add/remove
O(nlogn) build Unless the data is special and Counting Sort works, in which case it's O(n). *
1k = ability to look up a specific kth smallest/largest element .
Notably, build cost is O(n), not O(n⋅Maintenance Cost). In general the optimal time it takes to build a data structure is at most O(n⋅Maintenance Cost), but it can be less.
Heap:
O(1) read k=0
O(logn) add/remove You might think removes from a Heap are more than \log n. However, you can remove an element from a Heap in \log n if you know where it is (its index), and you can imagine storing a HashMap to keep track of that without adding any extra runtime complexity. *
O(n) build, notably not O(n log n).
Lookup Median See the Sliding Window Median problem. This is notably different from looking up a fixed L, because the index is variable and really depends on n. * :
O(1) read k=n/2
O(logn) add/remove
O(n) build
Lookup fixed k=L Uses a heap; see top K elements problem. * :
O(1) read k=L
O(logn) add/remove
O(n) build
In this kind of data structure, elements can be added or removed from the stream at any time. Note that "data streams" are similar - they're easier since they only have an add operation. *
We can predict the costs here by figuring out the normal cost of finding the value, and dividing by n.
sum-window = ability to look up the sum of the window.
Computing a sum costs O(n), and dividing by n we get O(1).
Indeed this is true; this is a trivial sliding window algorithm.
median-window = ability to look up the median of the window.
Computing a median k value has Maintenance Cost O(logn), and dividing by n we get O(logn).
This is indeed the complexity we get in the hourglass heap solution to Sliding Window Median! It just requires a heap deletion operation in logn time which is relatively easy to do, although not usually built into Heaps (usually they lazily delete elements when they read, which doesn't work here).
max-window = ability to look up the max value in the window.
Finding a maximum over n elements takes O(n), so dividing by n we get O(1).
This is somewhat surprising! But it is indeed the solution we find with the monotonic queue solution to Sliding Window Max!
Prefix problems:
prefix-simple = ability to check for a string prefix of a fixed string.
This is a trivial problem because it only involves 1 string; it's just here so you can see we can multiply out the per-element cost to the other problems and get Tries etc.
To swap out the string with another string, we need to replace m characters.
Notice that this gives O(1) maintenance per character.
prefix = ability to check for a string prefix of any of the given strings in a set.
This is the typical Trie solution.
We can multiply out the O(1) Maintenance Cost per character to get this cost.
Substring problems:
Notice the prefix problem can be turned into the substring problem by simply framing it as a Sliding Window version of the same problem. The maintenance cost per element is 1 for prefixes, so it should also be 1 for substrings, and we'd expect O(m) per element for substrings. This is indeed what you get - KMP and Aho Corasick data structures.
substring-simple = ability to check for a substring of a fixed string.
If we assume O(1) cost per character, we get O(m) here. This is the KMP solution!
substring = ability to check for a substring of any of the given strings in a set.
If we assume O(1) cost per character, we get O(k) here per avg string comparison, times the n strings. This is essentially O(m) like in the other problems, but aggregated over multiple strings.
This is the Aho Corasick solution!
disjoint-set = ability to lookup if two elements are in the same set.
This includes ability to merge sets, otherwise this would be trivial. A naive solution puts the maintenance cost at O(n). However, if you apply a few heuristics, you can get this to O(α(n)) - this is known as the Union Find data structure.
The Soft Heap does slightly better on a few of the operations, but is still bounded by this maintenance cost.
Disjoint Set / Union Find
create set O(1)
merge sets O(α(n))
add element O(α(n))
check membership O(α(n))
Soft Heap
create set O(1)
merge sets O(1)
add element O(log1/ϵ)
check membership (really, find-min) O(1)