That's a good insight. I had always thought the key to good algorithm / data structure design was to use all the information present in the data set. For example, if you know a list is sorted, you can use binary sort. But perhaps choosing how much of it to omit is key, too. It comes up less often, however. I can't think of a simple example.
> But perhaps choosing how much of it to omit is key, too. It comes up less often, however. I can't think of a simple example.
An example of that is a linked list with no particular sort order. By not caring about maintaining an order the insertion appends or preprends a node and is O(1).
As soon as you have to maintain any additional invariant, the insertion cost goes up. Either directly or amortized.
A real world analogue is detective stories that work by adding irrelevant details and itβs up to the reader to filter down to the truly important details to solve the case.
To generalize it, if figuring out what information is important is more expensive than assuming none of it is, better to simplify.
