What exactly does augmentation mean in computer science? [closed]

Question

I heard about cases where adding an extra requirement to a binary search (for example) can be called augmentation.

Is any increase in complexity of an algorithm considered augmentation?

Thanks

Answer 1

Augmentation usually means a fancy name for an extension. In computer science there are many fundamental, well-studied concepts, algorithms or data structure. These concepts are crucial to solve many real problems, but sometimes you have to add some additional functionality to the main idea.

Let's assume that you want to manage a set of numbers with standard insert/delete and in addition you want to efficiently count number of items in the set smaller than given number k.

In order to do that, you can implement a standard (balanced) binary search tree and in addition, in every node, store the number of nodes in the left subtree of that node (which denotes the number of smaller items) and keep track of that counter during insert/delete. Then if you want to return number of items smaller than k, you simply find k in the tree, and return k's counter. That's an augmentation.