algorithm - Why is insertion sort not dynamic programming -

algorithm - Why is insertion sort not dynamic programming -

a dynamic programming problem has optimal substructure , has solution can described recurrence relation.

a sorted list add-on of element sorted list, insertion sort has optimal substructure. recurrence relation described

sorted_list_n = sorted_list_n-1 + next element

so why isn't insertion sort considered dynamic programming algorithm? understand how applied in fibonacci numbers , in edit distance, not beyond that.

a given problem can solved using dynamic programming (dp) if problem has next 2 properties.

1) overlapping sub problems (osp)

2) optimal sub-structure (oss)

even though insertion sort algorithm has optimal sub-structure property, not have overlapping sub problems property. bit elaborated explanation follows..

in, fibonacci numbers calculation case, having above mentioned 2 properties.

osp : fib(5) calculation has fib(3) subproblem. @ same time, fib(4) calculation has fib(3) subproblem. fib(5) = fib(4) + fib(3). if blindly calculate fib(5) out dp technique, end calculating fib(3) twice (one fib(4) , 1 fib(3) itself). here, 1 of overlapping subproblems fib(3)

oss : in same way, if can calculate solution fib(4) , fib(3) optimally, solution fib(5) can calculated optimally. because fib(5) sum of fib(4) , fib(3).

now, allow seek check whether these 2 properties exist in insertion sort or not. allow sorting array of numbers {5, 2, 3, 1}.

osp : according recurrence thinking subproblems follows..

{5, 2, 3, 1}

{5, 2, 3}

{5, 2}

{5}

if observe closely, can see there no 2 subproblems similar. means overlapping sub problems property not exist.

oss : if can sort array of size (n-1) optimally, can sort array of size (n) optimally. optimal sub-structure property exist.

in summary, insertion sort algorithm not have overlapping sub problems property. hence not dp solution.

algorithm sorting dynamic-programming