MHB Calculating the Cost of Insertion Sort: O(n)

[evinda]

Hello! (Wave)

I am looking at the algorithm of the Insertion Sort:

Input: $A[1 \dots n]$ $\leftrightarrow$ a sequence of $n$ numbers

for j<-2 to n
    key<-A[j]
    i<-j-1
    while (i>0 and A[i]>key)
            A[i+1]<-A[i]
            i<-i-1
    end
    A[i+1]<-key
end

I want to calculate the cost of this algorithm. I thought that I could do I do it like that:

The "for" loop runs $n-2+1=n-1$ times, there are $3$ commands: key<-A[j],j<-j-1, A[i+1]<-key,the "while" loops run at most $n-1$ times and in the "while" loop,there are 2 commands: A[i+1]<-A,i<-i-1.

So,the cost is: $3(n-1)+2(n-1)=5n-5=5(n-1)= O(n)$

Could you tell me if it is right or if I have done something wrong? (Thinking)(Worried)

 

[M R]

Hello! (Wave)

I am looking at the algorithm of the Insertion Sort:

Input: $A[1 \dots n]$ $\leftrightarrow$ a sequence of $n$ numbers

for j<-2 to n
    key<-A[j]
    i<-j-1
    while (i>0 and A[i]>key)
            A[i+1]<-A[i]
            i<-i-1
    end
    A[i+1]<-key
end

I want to calculate the cost of this algorithm. I thought that I could do I do it like that:

The "for" loop runs $n-2+1=n-1$ times, there are $3$ commands: key<-A[j],j<-j-1, A[i+1]<-key,the "while" loops run at most $n-1$ times and in the "while" loop,there are 2 commands: A[i+1]<-A,i<-i-1.

So,the cost is: $3(n-1)+2(n-1)=5n-5=5(n-1)= O(n)$

Could you tell me if it is right or if I have done something wrong? (Thinking)(Worried)

What does this do?

a=0
for i=1 to 10
    j=0
    while j<10
       a=a+1
       j=j+1
print a

 

[I like Serena]

Hi! ;)

If an outer loop runs $n$ times and an inner loop also runs $n$ times, then the inner loop is executed $n\cdot n=n^2=O(n^2)$ times.

 

[evinda]

Hi! ;)

If an outer loop runs $n$ times and an inner loop also runs $n$ times, then the inner loop is executed $n\cdot n=n^2=O(n^2)$ times.

A ok! So,is the cost in our case $3 \cdot 2 \cdot (n-1)^2$ ? (Thinking)

 

[I like Serena]

A ok! So,is the cost in our case $3 \cdot 2 \cdot (n-1)^2$ ? (Thinking)

That depends on how accurate you want to be.
The order is definitely $O(n^2)$.

But if you want to say more about the constant, you're still slightly off.
The outer loop has 3 instructions that are executed $(n-1)$ times.
Added to that, the last time the inner loop is executed $(n-1)$ times with 2 instructions. But on average it is executed $\frac 12(n-1)$ times for every time the outer loop is executed.

So that makes $3(n-1) + 2 \cdot (n-1)\cdot \frac 12(n-1) = n^2 + n - 1 \quad\propto n^2$ instructions.
As you can see, this is not $\quad\propto 6n^2$, which is what you were getting at. (Nerd)

Furthermore, you are only counting explicit assignments. How about the conditions, and how about the implicit assignments? Or are you supposed to ignore those?

 

[evinda]

The outer loop has 3 instructions that are executed $(n-1)$ times.
Added to that, the last time the inner loop is executed $(n-1)$ times with 2 instructions. But on average it is executed $\frac 12(n-1)$ times for every time the outer loop is executed.

So that makes $3(n-1) + 2 \cdot (n-1)\cdot \frac 12(n-1) = n^2 + n - 1 \quad\propto n^2$ instructions.
As you can see, this is not $\quad\propto 6n^2$, which is what you were getting at. (Nerd)

Furthermore, you are only counting explicit assignments. How about the conditions, and how about the implicit assignments? Or are you supposed to ignore those?

Could you explain me further why it is 3(n-1)+ 2 (n-1)*1/2 (n-1) ? I haven't really understood it.. (Worried)

Oh,sorry!I forgot to count also the conditions and the implicit assignments.. (Blush) But...how can I find the cost of them? (Thinking)

 

[Evgeny.Makarov]

To determine time complexity, you need to decide whether you are interested in worst-case complexity or average-case complexity, whether you need a precise number or big-O estimate, and in the former case which exactly operations you are counting.

 

[evinda]

To determine time complexity, you need to decide whether you are interested in worst-case complexity or average-case complexity, whether you need a precise number or big-O estimate, and in the former case which exactly operations you are counting.

I want to find the big-O estimate..So do I have to count,for example,also the conditions? (Thinking)

 

[Evgeny.Makarov]

Well, let's start from the beginning. Let $A$ be an array of $n$ elements where an index ranges from $0$ to $n-1$. Consider the following code for counting positive elements of $A$.

i = 0;
num = 0;
while (i < n) {
  if (A[i] > 0) num = num + 1;
  i = i + 1;
}

Suppose a comparison takes $c$ μs (microseconds), and assignment takes $a$ μs. Please answer the following questions.

1. What is the total number of assignments the algorithm makes, including the initial two?
2. What is the total number of comparisons?
3. What is the total time the algorithm takes, in μs, assuming the time is spent on assignments and comparisons only?
4. What is the optimal big-O estimate on the total time? ($O(2^n)$ will work, but it's not optimal.)
5. Does the big-O estimate change if you assume that only assignments take time and comparisons are instantaneous?
6. Does the big-O estimate change if you assume that only comparisons take time and assignments are instantaneous?
7. Does the big-O estimate depend on the values of $a$ and $c$?
8. Does the big-O estimate change if you take jump instructions into account (i.e., the jump after the final instruction of the loop to the beginning of the loop)?
9. What value is essential for the big-O estimate?

Can you now answer your question?

I want to find the big-O estimate..So do I have to count,for example,also the conditions?

 

[evinda]

Well, let's start from the beginning. Let $A$ be an array of $n$ elements where an index ranges from $0$ to $n-1$. Consider the following code for counting positive elements of $A$.

i = 0;
num = 0;
while (i < n) {
  if (A[i] > 0) num = num + 1;
  i = i + 1;
}

Suppose a comparison takes $c$ μs (microseconds), and assignment takes $a$ μs. Please answer the following questions.

1. What is the total number of assignments the algorithm makes, including the initial two?
2. What is the total number of comparisons?
3. What is the total time the algorithm takes, in μs, assuming the time is spent on assignments and comparisons only?
4. What is the optimal big-O estimate on the total time? ($O(2^n)$ will work, but it's not optimal.)
5. Does the big-O estimate change if you assume that only assignments take time and comparisons are instantaneous?
6. Does the big-O estimate change if you assume that only comparisons take time and assignments are instantaneous?
7. Does the big-O estimate depend on the values of $a$ and $c$?
8. Does the big-O estimate change if you take jump instructions into account (i.e., the jump after the final instruction of the loop to the beginning of the loop)?
9. What value is essential for the big-O estimate?

1. There are at most $2n+2$ assignments
2.There are $2n+1$ comparisons
3. $(2n+2) a+ (2n+1)c$
4.The optimal big-O estimate on the total time is $O(n)$
5.The big-O estimate does not change if we assume that only assignments take time and comparisons are instantaneous.
6.The big-O estimate does not change if we assume that only comparisons take time and assignments are instantaneous.
7.The big-O estimate does not depend on the values of $a$ and $c$.
8.The big-O estimate does not change if we take jump instructions into account.
9.Isn't it the term with the highest degree?Or am I wrong? (Thinking)

 

[evinda]

Can you now answer your question?

So,is it :

$$(n-1)((3+2(n-1))a+2(n-1)c)$$

? (Thinking)

 

[Evgeny.Makarov]

2.There are $2n+1$ comparisons

It's good that you counted the last loop guard comparison $n<n$.

9.Isn't it the term with the highest degree?

I was thinking more like, the number of iteration is what counts in the big-O estimate, not the number of instructions in each loop or the time individual instructions take.

So,is it :

$$(n-1)((3+2(n-1))a+2(n-1)c)$$

What exactly are you asking about this quantity? You have not responded to my questions. I asked if you can answer your question whether you need to count comparisons, based on your response to my 9 questions. Also, I asked if you need the worst-case complexity or average-case complexity. The worst-case happens when the input array is sorted in descending order, so the $j$th element (which is assigned to "key") is less than all previous elements, the condition "A > key" is always true and the inner loop is executed the maximal number of times.

There are two ways to find a big-O complexity estimate. One is to find the exact number of operations and then find the optimal big-O estimate of that function. I assume you were asking whether the quantity above is the exact time spent on assignments and comparisons. But then it is important to know if you count the maximum or average number of operations. In post #1 you talked about the worst case ("at most $n−1$ times"), while in post #5 I like Serena used the average number of times the inner loop runs. (In fact, the average number is not obvious and requires some analysis, though the answer is probably correct.) If you are interested in an expression like you wrote, then it is important whether it's worst case or average case.

However, after writing this precise expression, you throw all of it out and only keep the highest degree of $n$ to get the big-O estimate. In fact, the decision you started with—which operations to count—is arbitrary because you always omit some operations (you don't know exactly which instructions a computer performs). So by counting a different set of instructions and performing a more careful analysis you would end up with a different function of $n$. Then again you would throw out most of its terms and coefficients and end up with the same big-O estimate. In fact, even the average vs worst case does not matter for this particular algorithm: both give $O(n^2)$, though for other algorithms these two complexities may be different. So in practice this first way of estimating complexity is not used.

The second way is to abstract away from unimportant details from the start and count only the number of iterations. As I like Serena wrote in post #3, the outer loop runs $O(n)$ times, and for each of those the inner loop runs $O(n)$ times, so the total time is $O(n^2)$.

 

[evinda]

It's good that you counted the last loop guard comparison $n<n$.

I was thinking more like, the number of iteration is what counts in the big-O estimate, not the number of instructions in each loop or the time individual instructions take.

What exactly are you asking about this quantity? You have not responded to my questions. I asked if you can answer your question whether you need to count comparisons, based on your response to my 9 questions. Also, I asked if you need the worst-case complexity or average-case complexity. The worst-case happens when the input array is sorted in descending order, so the $j$th element (which is assigned to "key") is less than all previous elements, the condition "A > key" is always true and the inner loop is executed the maximal number of times.

There are two ways to find a big-O complexity estimate. One is to find the exact number of operations and then find the optimal big-O estimate of that function. I assume you were asking whether the quantity above is the exact time spent on assignments and comparisons. But then it is important to know if you count the maximum or average number of operations. In post #1 you talked about the worst case ("at most $n−1$ times"), while in post #5 I like Serena used the average number of times the inner loop runs. (In fact, the average number is not obvious and requires some analysis, though the answer is probably correct.) If you are interested in an expression like you wrote, then it is important whether it's worst case or average case.

However, after writing this precise expression, you throw all of it out and only keep the highest degree of $n$ to get the big-O estimate. In fact, the decision you started with—which operations to count—is arbitrary because you always omit some operations (you don't know exactly which instructions a computer performs). So by counting a different set of instructions and performing a more careful analysis you would end up with a different function of $n$. Then again you would throw out most of its terms and coefficients and end up with the same big-O estimate. In fact, even the average vs worst case does not matter for this particular algorithm: both give $O(n^2)$, though for other algorithms these two complexities may be different. So in practice this first way of estimating complexity is not used.

The second way is to abstract away from unimportant details from the start and count only the number of iterations. As I like Serena wrote in post #3, the outer loop runs $O(n)$ times, and for each of those the inner loop runs $O(n)$ times, so the total time is $O(n^2)$.

So,if I do it with the second way and I want to find the worst-case complexity,do I have to count only the maximum number that the outer and inner loop run and multiply them?

And,if I want to find the average-case complexity,I multiply the number that the outer loop runs with the average number that the inner loop runs?So,is it in our case: $\displaystyle{ \frac{(n-1) \cdot (n-1)}{2}}$ ?

Or have I understood it wrong? (Worried) (Thinking)