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 Θ(n^{2})" is a bit sloppy because it's not *insertion sort itself* that's Θ(n^{2}), 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 Θ(n^{2}), which happens on a reverse-sorted list. Assuming the input is a random permutation of n elements, the average-case runtime is also Θ(n^{2}). Those more precise statements are probably better to make than "insertion sort is O(n)" or "insertion sort is Θ(n^{2})," 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