Complexity asymmetry

To decide which algorithm is best to use, engineers consider the complexities in memory and computations, and based on the trade-offs between the two and the specific usage of operations (search, insert, etc.), they decide which algorithm is the most applicable for a specific problem.

Web3 and on-chain programs are not different, but they introduce one more variable for engineers to consider: on-chain complexity.

On-chain complexity can be very different from the overall complexity. You can have O(1) search and insert operations on-chain, while the general O(N) complexity is shifted fully onto the off-chain layer.

• Sorted linked list. That's a surprisingly frequently used data structure in web3, and the reason behind this is that even though the algorithm for finding & inserting an element into it is generally inefficient due to O(n) for both operations, it is possible to turn both operations into O(1) on-chain, while shifting the O(n) off-chain, making it extremely efficient for on-chain purposes.
  • Here's how: let the client-side find the position of the element and send it in, and have your program only check it. That way, the client-side would spend O(n) computations to find the position, but your program would benefit from it by optimizing itself into O(1) complexity by just checking a few positions in a constant time.
  • Monaco Protocol's order book is this list. The book is a fixed set of cells in one account, and each order points to its price neighbors by cell number. The client computes where the new order goes and sends "after this order". The program checks three things: the left neighbor is not cheaper, the right neighbor is cheaper, both are alive. That check costs the same at any depth, and the capacity is fixed, so nobody can inflate the book past what fits.
• Compressed NFTs (Bubblegum) do it for memory optimization. A million NFTs are one account with one merkle root hash. The full merkle tree lives off-chain with an indexer. To change one NFT, the client brings the leaf and about twenty hashes along its path, and the program recomputes the root and compares. On-chain memory is O(1), the on-chain check is O(log n), and the O(n) part lives with the indexer.

Merkle trees such as in Bubblegum are the worst data structure you can imagine using for a normal traditional program. With web3 programs however, it is one of the most popular and frequently used ones.

Important to remember: the reason why we don't want any high complexity (higher than O(logN)) on-chain, is because it makes it easy to just spam the program with data and make it no longer fit the compute limit, after which nobody could use it. This is also frequently referred to as "DOS attack"