About insertion sort time complexity

In my text book, it says that time complexity of insertion sort is big theta n^2. I couldn't understand that since insertion sort's best case is big O n. I know big theta is lower and upper bound both. So is it correct that time complexity of insertion sort is big O n^2 not big theta n^2? Sorry to my poor english thx.

You have to be careful when talking about "the" time complexity of a piece of code, because there isn't one single time complexity you can point at. A piece of code can have a best-case time complexity, a worst-case time complexity, an average-case time complexity, etc., and they don't have to all be the same.

Saying that "insertion sort is Θ(n2)" is a bit sloppy because it's not insertion sort itself that's Θ(n2), but rather its worst-case runtime. Typically, if you say that a piece of code is O(f(n)), you're saying that its runtime is O(f(n)), and usually that implies that you're talking about the worst-case runtime.

It's true that the best-case runtime of insertion sort is Θ(n), which happens when the input is already sorted. The worst-case runtime is Θ(n2), which happens on a reverse-sorted list. Assuming the input is a random permutation of n elements, the average-case runtime is also Θ(n2). Those more precise statements are probably better to make than "insertion sort is O(n)" or "insertion sort is Θ(n2)," since they capture more about the runtime of insertion sort.

Do note that just using O, Θ, or Ω doesn't automatically mean that you're talking about best/worst/average case complexity. You can use Θ notation to talk about a best-case, worst-case, or average-case runtime, for example.

When generally speaking of 'the time complexity of an algorithm' one usually speaks of all types of inputs, not restricted to e.g. worse-case or best-case scenarios.

In this general case, for all types of inputs, one case (the worst-case) is enough to determine the complexity class to be the worse class.

So it does not help that the best-case here yields Θ(n) when we speak of the time complexity for all inputs.

However you can also analyze an algorithm explicitly for a specific scenario, e.g. only for the best-case or worst-case and so on. Then you restrict the algorithm and only allow such types of input.

O vs. Θ isn't worst-case vs. all cases; it's the difference between <= and =.

For example the algorithm Merge sort is O(n^2), but it's not Θ(n^2) because it's faster than that.

Average case is often as bad as worst case asymptotically and the worst case for insertion sort is n^2. CLRS has a very good theory on finding worst case for insertion sort

0 Comment

NO COMMENTS

LEAVE A REPLY

Captcha image