Big theta notation for insertion sort algorithm

Question

I study the asymptotic notation from the book, and I cannot understand what the author means. I know that if f(n) = Θ(n^2) then f(n) = O(n^2) . However, from the author’s words, I understand that for the insertion sorting algorithm, f(n) = Θ(n) and f(n)=O(n^2) .

Why? Does a large omega or a large theta change with different inputs?

He says that:

“However, the estimate Θ (n ^ 2) associated with the worst-time insertion sorting does not mean that Θ (n ^ 2) is tied to each input at the time the input is entered.

However, for the big-oh notation, it is different. What does he mean? What is the difference between the two?

I'm so confused. I will copy it below:

Since the O-notation describes the upper bound, when we use it to bind the worst-case time to the algorithm, we have an estimate of the running time of the algorithm at each input. Thus, O (n ^ 2), associated with the worst execution time of the sort insert, also refers to its launch time at each input. Θ (n ^ 2), associated with the worst execution time of the insertion sort, however, does not mean that Θ (n ^ 2), associated with the execution time of the insertion sort on each input. For example, when an input is already sorted, insertion is sorted at Θ (n) time.

Answer 1

Is a big omega or a big theta with different inputs changed?

Yes. To give a simpler example, consider linear searching in an array from left to right. In the worst and middle case, this algorithm takes f (n) = a × n / 2 + b the expected steps for some constants a and b. But when the left element is guaranteed that you always hold the key you are looking for, it always takes + b steps.

Since Θ denotes a strict estimate and Θ (n)! = Θ (n²), is different for the two input types.

EDIT : for both Θ and large output O on the same input, yes, that’s completely possible. Consider the following (supposedly trivial) example.

When we set n to 5, then n = 5 and n <6 are true. But when we set n to 1, then n = 5 is false, and n <6 is still true.

Similarly, big-O is only the upper bound, as is <on numbers, and Θ is a strict bound as =.

(Actually, Θ looks more like a <n <b for constants a and b, that is, it defines something similar to a range of numbers, but the principle is the same.)

Answer 2

Refer to CLRS 3 Page -44 (Asymptotic Notation, Functions, and Runtime) It says -

Even if we use asymptotic notation in relation to the running time of the algorithm, we need to understand which running time we mean . Sometimes we are interested in the worst-case run time. Often, however, we wish to characterize the running time no matter what the input. In other words, we often wish to make a blanket statement that covers all inputs, not just the worst case.

Excerpts from the above paragraph:

• The worst case provides the maximum limit for the running time of the algorithm. Thus, O (n ^ 2), associated with the worst execution time of the insertion sort, also refers to its execution time at each input.

• But Theta(n^2) , associated with the worst execution time for insert insertion, does not mean that Theta(n^2) tied to insertion sort completion time at each input. Since the best time to perform insertion sorting is given by Theta(n) . (When the list is already sorted)

• Usually we record the time complexity of the worst case algorithm, but when the best case and the average case are reported, the time complexity varies depending on these cases.

Answer 3

we have an estimate for the running time of the algorithm at each input

This means that if there is a set of inputs with runtime n^2 , while others have less, then the algorithm is O(n^2) .

Θ (n ^ 2), associated with the worst-time insertion sort execution, however, does not mean that Θ (n ^ 2), the operation-time insertion sort on each input

He says the opposite is not true. If the algorithm is O(n^2) , this does not mean that each individual input will work with quadratic time.

Answer 4

My academic theory of insertion sorting algorithm is far from the past, but from what I understand in your copy-paste:

The big O signs always describe the worst case, but big-Theta describes some kind of average for typical data.

take a look at this: What is the difference between Θ (n) and O (n)?