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
