Search code examples
algorithmcomplexity-theorybig-oinsertion

What is the best description of the run time complexity of insertion sort


I have understood it to be quadratic, but I am taking a multiple choice practice test for discrete math and the only four options are:

a) logarithmic

b) linear

c)linearithmic

d)polynomial


Solution

  • a) logarithmic = O(log n)

    b) linear = O(n)

    c) linearithmic = O(n log n)

    d) polynomial = O(nk)

    So O(n2) would be polynomial.