CODEWITHSUNDEEP
algorithmcomplexity-theorybig-oinsertion
Joe
Joe

Reputation: 512

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

Upvotes: 0

Views: 189

Answers (2)

Peter Webb
Peter Webb

Reputation: 691

Inserting a new value into a list or tree of sorted values is O(log n).

Easiest to see with a straight sorted list. Lets say you want to insert x. Find the value at [n/2]. If this is greater than x, then the correct location lies on the left half. If [n/2] is less than x, then the correct location lies on the right. Repeat, checking the middle value each time. Each step halves the size of the interval to check until you find the correct value, giving logarithmic time for the insertion.

An insertion into a tree is similar; you have to traverse the tree to the correct node position, which requires traversing the average depth of the tree, which is proportional to log n

Upvotes: 0

Bernhard Barker
Bernhard Barker

Reputation: 55649

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.

Upvotes: 1

Related Questions