## Discussion Forum

Que. | In a permutation a1.....an of n distinct integers, an inversion is a pair (ai, aj) such that i < j and ai > aj. What would be the worst case time complexity of the Insertion Sort algorithm, if the inputs are restricted to permutations of 1.....n with at most n inversions? |

a. | Θ (n^2) |

b. | Θ (n log n) |

c. | Θ (n^1.5) |

d. | Θ (n) |

Answer:Θ (n) |