Q: why wont my code checkout var insert = function(array, rightIndex, value) { for(var j = rightIndex; j > 0 && array[j-1] > value; j--) { array[j] = array[j-1]; } array[j] = value; }; var insertionSort = function(array) { for(var i = 0; i < array.length; i++){ insert(array, i, array[i]); } }; var array = [22, 11, 99, 88, 9, 7, 42]; insertionSort(array); println("Array after sorting: " + array); Program.assertEqual(array, [7, 9, 11, 22, 42, 88, 99]);

You shouldn't modify functions that they have already completed for you, i.e. insert() , if you want to pass the challenges. If you change the other functions that have been provided for you, the grader won't be able to tell if your code works or not (It is depending on the other functions to behave in a certain way).

Q: what about Omega can I say that insertion sort is Ω(n) or it is constant Ω(n^0)=Ω(1) ? Because in some cases, if it is sorted, we only need to add it at the end, and this is the least possible Big-Ω (Big-Omega) notation https://www.khanacademy.org/computing/computer-science/algorithms/asymptotic-notation/a/big-big-omega-notation

There is no single answer. It depends on the scenario i.e. best case, worst case, average case, etc. Recall that: By definition, if f(n) is Big Theta(g(n)) then f(n) is Big O(g(n)) and f(n) is Big Omega(g(n)). Since the running time of insertion sort, in the best case, is Big Theta(n), it is also Big Omega(n). By similar logic, it is: - Big Omega(n) in the "almost sorted case". - Big Omega(n^2) in the worst case - Big Omega(n^2) in the average case

Q: Could we also say the runtime is O(n) best case? Since best is when the array is already sorted, so it will take no longer than linear time.

*Short Answer*: Yes *Long Answer*: By definition, if f(n) is Big Theta(g(n)) then f(n) is Big O(g(n)) and f(n) is Big Omega(g(n)). Since the running time of insertion sort, in the best case, is Big Theta(n), it is also O(n).

Q: Thank you for this awesome lecture. Would it be possible to include a section for "loop invariant"?

Loop invariants are really simple (but finding the right invariant can be hard): They are statements that must be true before the loop and after the loop. For insertion sort we have the loop invariant: "After the kth iteration, elements a[0] to a[k] are sorted" Before we start the first loop (we have perfomed 0 iterations) k=0 thus this is true: "After iteration 0, elements a[0] to a[0] are sorted" i.e. the first element is trivially sorted In the first loop we insert a[1] in order on a[0]. After we complete the loop the first time (k=1 ) this is true: "After iteration 1, elements a[0] to a[1] are sorted" In the second loop we insert a[2] in order on a[0] to a[1] After we complete the loop the second time (k=2 ) this is true: "After iteration 2, elements a[0] to a[2] are sorted" ... In the kth loop we insert a[k] in order on a[0] to a[k-1] After we complete the loop the kth time this is true: "After iteration k, elements a[0] to a[k] are sorted" ... On the last loop, ( the (n-1)th loop for an array with n elements), we insert a[n-1] in order on a[0] to a[n-2] After we complete the loop the (n-1)th time this is true: "After iteration n-1, elements a[0] to a[n-1] are sorted" So the loop invariant proves that insertion sort actually sorts the array, because it tells us that after the last iteration elements a[0] to a[n-1] are sorted

Q: Can we make a blanket statement that insertion sort runs it omega(n) time?

Yes, you could. In the best case (array is already sorted), insertion sort is omega(n). You can't possibly run faster than the lower bound of the best case, so you could say that insertion sort is omega(n) in ALL cases.

Q: _c * (n-1+1)((n-1)/2) = cn^2/2 - cn/2_ Can someone explain to me how the formula is derived? For example: why (n-1+1) and why divide by 2?

(n-1+1)((n-1)/2) is the sum of the series of numbers from 1 to n-1. It uses the stand arithmetic series formula. Here's the derivation: If S is the sum of the numbers 1 to k: S = 1 + 2 + 3 + ... + k-2 + k-1 + k And then in reverse S = k + k-1 + k-2 + ... + 3 + 2 + 1 If we add them we get: 2S = (1+k)+(2+k-1)+(3+k-2)+...+(k-2+3)+(k-1+2)+(k+1) 2S = (1+k) + (1+k) + (1+k) ... k times 2S = (1+k) * k So: S= (1+k)/2 * k Or S= (first term + last term)/2 * number of terms For a video see: https://www.khanacademy.org/math/precalculus/x9e81a4f98389efdf:series/x9e81a4f98389efdf:arith-series/v/sum-of-arithmetic-sequence-arithmetic-series If we substitute n-1 for k we get: S = (n-1 + 1)/2 * (n-1) Which is the same as the above. Hope this makes sense

Q: I don't understand how O is (n^2) instead of just (n); I think I got confused when we turned the arithmetic summ into this equation: c⋅(n−1+1)((n−1)/2)=cn^2/2−cn/2 I inferred from the text that it takes for granted some mathematical theorem that I have no idea of. Is that what's happening? Thanks!

In general the sum of 1 + 2 + 3 + ... + x = (1 + x) * (x)/2 For more info on how it is derived see this to understand what an arithmetic sequence is: https://www.khanacademy.org/math/precalculus/seq-induction/sequences-review/v/arithmetic-sequences and this to understand how the formula was derived: https://www.khanacademy.org/math/precalculus/seq-induction/seq-and-series/v/alternate-proof-to-induction-for-integer-sum

Q: No sure why following code does not work. I keep getting "A function is taking too long..." message. Any help? var insert = function(array, rightIndex, value) { for(var j = rightIndex; j >= 0 && array[j] > value; j--) { array[j + 1] = array[j]; } array[j + 1] = value; }; var insertionSort = function(array) { for (var i=1; i < array.length ; i++){ insert (array,i,array[i]); } }; var array = [22, 11, 99, 88, 9, 7, 42]; insertionSort(array);

The insertionSort function has a mistake in the insert statement (Check the values of arguments that you are passing into it). When your insertionSort function reaches the end of your array its call to insert is adding a copy of the last element of the array onto the end of itself. This causes the array to increase in size, which makes the condition in the for loop true. It repeats this forever until you get the error message. Good Luck

Question 1

I am not able to understand this situation- "say 17, from where it's supposed to be when sorted? "
how running time can be 17⋅c⋅(n−1). for this situation. Please make it clear.

Accepted Answer

Basically, it is saying:
-Suppose the insert function, at most, performs 17 comparisons each time it is called (because the array is almost sorted )
-A comparison costs c and we perform 17 of them per insert, so the cost of an insert is 17 * c
-The insertion sort function calls the insert  function on each of the  n-1 elements (we get the 1st element for free), so:  
cost of an insert * number of inserts = (17 * c) * (n-1)

Hope this makes sense

Question 2

why wont my code checkout

var insert = function(array, rightIndex, value) {
    for(var j = rightIndex; j > 0 && array[j-1] > value; j--)     {
    array[j] = array[j-1];
    }   
    array[j] = value; 
};

var insertionSort = function(array) {
    for(var i = 0; i < array.length; i++){
        insert(array, i, array[i]);
    }
};

var array = [22, 11, 99, 88, 9, 7, 42];
insertionSort(array);
println("Array after sorting: " + array);
Program.assertEqual(array, [7, 9, 11, 22, 42, 88, 99]);

Accepted Answer

You shouldn't modify functions that they have already completed for you, i.e. insert() , if you want to pass the challenges.  If you change the other functions that have been provided for you, the grader won't be able to tell if your code works or not (It is depending on the other functions to behave in a certain way).

Question 3

what about Omega can I say that insertion sort is Ω(n)
or it is constant Ω(n^0)=Ω(1) ?

Because in some cases, if it is sorted, we only need to add it at the end, and this is the least possible

Big-Ω (Big-Omega) notation
https://www.khanacademy.org/computing/computer-science/algorithms/asymptotic-notation/a/big-big-omega-notation

Accepted Answer

There is no single answer. It depends on the scenario i.e. best case, worst case, average case, etc.

Recall that:
By definition, if f(n) is Big Theta(g(n)) then f(n) is Big O(g(n)) and f(n) is Big Omega(g(n)).

Since the running time of insertion sort, in the best case, is Big Theta(n), it is also Big Omega(n).

By similar logic, it is:
- Big Omega(n) in the "almost sorted case". 
- Big Omega(n^2) in the worst case
- Big Omega(n^2) in the average case

Question 4

Could we also say the runtime is O(n) best case? Since best is when the array is already sorted, so it will take no longer than linear time.

Accepted Answer

*Short Answer*:
Yes

*Long Answer*:
By definition, if f(n) is Big Theta(g(n)) then f(n) is Big O(g(n)) and f(n) is Big Omega(g(n)).

Since the running time of insertion sort, in the best case, is Big Theta(n), it is also O(n).

Question 5

Thank you for this awesome lecture. Would it be possible to include a section for "loop invariant"?

Accepted Answer

Loop invariants are really simple (but finding the right invariant can be hard): 
They are statements that must be true before the loop and after the loop.

For insertion sort we have the loop invariant:
"After the kth iteration, elements a[0] to a[k] are sorted"

Before we start the first loop (we have perfomed 0 iterations) k=0 thus this is true:
"After iteration 0, elements a[0] to a[0] are sorted" i.e. the first element is trivially sorted

In the first loop we insert a[1] in order on a[0]. 
After we complete the loop the first time (k=1 ) this is true:
"After iteration 1, elements a[0] to a[1] are sorted"

In the second loop we insert a[2] in order on a[0] to a[1] 
After we complete the loop the second time (k=2 ) this is true:
"After iteration 2, elements a[0] to a[2] are sorted"

...
In the kth loop we insert a[k] in order on a[0] to a[k-1] 
After we complete the loop the kth time this is true:
"After iteration k, elements a[0] to a[k] are sorted"

...
On the last loop, ( the (n-1)th loop for an array with n elements),
we insert a[n-1] in order on a[0] to a[n-2]
After we complete the loop the (n-1)th time this is true:
"After iteration n-1, elements a[0] to a[n-1] are sorted"

So the loop invariant proves that insertion sort actually sorts the array, because it tells us that after the last iteration elements a[0] to a[n-1] are sorted

Question 6

Can we make a blanket statement that insertion sort runs it omega(n) time?

Accepted Answer

Yes, you could. In the best case (array is already sorted), insertion sort is omega(n). You can't possibly run faster than the lower bound of the best case, so you could say that insertion sort is omega(n) in ALL cases.

Question 7

_c * (n-1+1)((n-1)/2) = cn^2/2 - cn/2_

Can someone explain to me how the formula is derived?
For example: why (n-1+1) and why divide by 2?

Accepted Answer

(n-1+1)((n-1)/2) is the sum of the series of numbers from 1 to n-1. It uses the stand arithmetic series formula.

Here's the derivation:
If S is the sum of the numbers 1 to k:
S = 1 + 2 + 3 + ... + k-2 + k-1 + k
And then in reverse
S = k + k-1 + k-2 + ... + 3 + 2 + 1 
If we add them we get:
2S = (1+k)+(2+k-1)+(3+k-2)+...+(k-2+3)+(k-1+2)+(k+1)
2S = (1+k) + (1+k) + (1+k) ... k times
2S = (1+k) * k
So:
S= (1+k)/2 * k
Or
S= (first term + last term)/2 * number of terms
For a video see:
https://www.khanacademy.org/math/precalculus/x9e81a4f98389efdf:series/x9e81a4f98389efdf:arith-series/v/sum-of-arithmetic-sequence-arithmetic-series

If we substitute n-1 for k we get:
S = (n-1 + 1)/2 * (n-1)
Which is the same as the above.

Hope this makes sense

Question 8

I don't understand how O is (n^2) instead of just (n); I think I got confused when we turned the arithmetic summ into this equation:
c⋅(n−1+1)((n−1)/2)=cn^​2/2−cn/2

I inferred from the text that it takes for granted some mathematical theorem that I have no idea of. Is that what's happening? Thanks!

Accepted Answer

In general the sum of 1 + 2 + 3 + ... + x = (1 + x) * (x)/2

For more info on how it is derived see this to understand what an arithmetic sequence is:
https://www.khanacademy.org/math/precalculus/seq-induction/sequences-review/v/arithmetic-sequences

and this to understand how the formula was derived:
https://www.khanacademy.org/math/precalculus/seq-induction/seq-and-series/v/alternate-proof-to-induction-for-integer-sum

Question 9

No sure why following code does not work. I keep getting "A function is taking too long..." message. Any help? 
var insert = function(array, rightIndex, value) {
    for(var j = rightIndex;
        j >= 0 && array[j] > value;
        j--) {
        array[j + 1] = array[j];
    }   
    array[j + 1] = value; 
};

var insertionSort = function(array) {
    for (var i=1; i < array.length ; i++){
        insert (array,i,array[i]);
    }
};

var array = [22, 11, 99, 88, 9, 7, 42];
insertionSort(array);

Accepted Answer

The insertionSort function has a mistake in the insert statement (Check the values of arguments that you are passing into it).

When your insertionSort function reaches the end of your array its call to insert is adding a copy of the last element of the array onto the end of itself. This causes the array to increase in size, which makes the condition in the for loop true. It repeats this forever until you get the error message.

Good Luck

Course: Computer science theory > Unit 1

Analysis of insertion sort

Want to join the conversation?