1. Write Insertion sort algorithm. Determine its complexity in Best, Average and Worst Case. Sort the following sequence in increasing order: 35, 37, 18, 15, 40, 12; Using Insertion Sort.

1. Write Insertion sort algorithm. Determine its complexity in Best, Average and Worst Case. Sort the following sequence in increasing order: 35, 37, 18, 15, 40, 12; Using Insertion Sort.

ANS 1. 

A recursive definition of a sequence specifies
 1) Initial conditions
 2) Recurrence relation
Example:
a0=0 and a1=3  Initial conditions
an = 2an-1 – an-2  Recurrence relation
an = 3n  Solution
Linear recurrence: Each term of a sequence is a linear function of
earlier terms in the sequence. For example:
a0 = 1 a1 = 6 a2 = 10
an = an-1 + 2an-2 + 3an-3
a3 = a0 + 2a1 + 3a2
= 1 + 2(6) + 3(10) = 43