4

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

Oleksiy
  • 37,477
  • 22
  • 74
  • 122
  • Perhaps this question should be migrated to http://programmers.stackexchange.com? It is a very useful question because there doesn't seem to be a clear definition of augmentation anywhere and this question comes out when searching google for '[augmentation computer science](https://www.google.com/search?q=augmentation+computer+science)' – icc97 Oct 27 '13 at 10:19

2 Answers2

4

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.

pkacprzak
  • 5,537
  • 1
  • 17
  • 37
  • 'Augmentation' was explained to me as 'strengthening' see this [comment](http://stackoverflow.com/questions/14994391/how-do-i-think-in-angularjs-if-i-have-a-jquery-background/15012542?noredirect=1#comment29088343_15012542) – icc97 Oct 27 '13 at 10:20
  • @icc97 yes, but I think that an `extension` is a more suitable word – pkacprzak Oct 27 '13 at 23:36
1

I wouldn't restrict it to adding complexity, but every addition to something (like Augumented Realtity) can be called an "Augmentation". I never saw any clear definition of "Augmentation" in computer science and I doubt there is one.

ssindelar
  • 2,833
  • 1
  • 17
  • 36