View theory topics
All divide and conquer algorithms divides the problem into sub problems, each of which is part of the original problem, and then perform some additional work to compute the final answer. As an example, merge sort algorithm operates on two sub-problems, each of which is half the size of the original and performs O(n) additional work for merging. This gives the running time equation. T(n) = 2T(n/2) + O(n) The following theorem can be used to determine the running time of divide and conquer algorithms. For a given program (algorithm), …