By law of Divide-and-Conquer, most algorithms that involve breaking problems down into a single subelement of itself uses binary tree as its data structure/abstract data type. Looking at the bread-and-butter algorithms like merge sort, binary search, a question popped up in my mind: why don’t we divide the problem up 3-way, or even 4-way? Wouldn’t that seem to be doing more at each level down the recursion and seem faster?

Note that the assumed topic is different from an* optimal binary search tree*, which is defined as a binary search tree for which the nodes are arranged on levels such that the tree cost is minimum. The following evaluates the plausibility of using *n-ary* trees where *n>2* to process divide-and-conquer problems.

Advertisements