Divide and Conquer Algorithm

Posted By on September 2, 2014

Download PDF
Binary Search Tree
Binary Search

Divide – break the problem into several subproblems that are similar to the original problem but smaller in size

Conquer – solve the subproblems recursively.

Base case: If the subproblem size is small enough (i.e., the base case has been reached) then solve the subproblem directly without more recursion.

Combine – the solutions to create a solution for the original problem

Analysis of recursive algorithms

Iterative algorithms can often be analyzed by counting instruction executions for some problem size n, as was done for the Insertion sort.

Recursive algorithms solve a problem based on recurring solution(s) to progressively smaller subproblem(s). Accurate analysis requires an accounting of this recurrence.

recurrence equation – describes the running time of a problem of size n of an algorithm that contains a recursive call to itself, in terms of the running time on smaller inputs of the same problem type.

T(n) = recurrence equation defining the running time on problem of size n

Binary Search Tree
Binary Search

Download PDF

Posted by Akash Kurup

Founder and C.E.O, World4Engineers Educationist and Entrepreneur by passion. Orator and blogger by hobby

Website: http://world4engineers.com