Yup 😂❤

yeah he said worst case scenario, you have to shift each of n characters, n times. so n x n = n^2

O looks at the worst case scenario: ie, all characters not sorted - we'll have to shift every character with every movement of the line (or the character we're looking at). If we looked at 1 character before, 1 shift (the character we just looked at) needs to be made for the 2nd character to be sorted. If there are 3 characters that are all unsorted, we will need to shift each character once in order to sort to the 3rd character. The math ends up being n^2 3 2 1 --> 1st sort ('3' is sorted) (1 * 1) 2 3 1 --> 2nd (2 and 3 shift to allow 2 and 3 to be sorted, 1 is not sorted yet) (2 chars /movements of the line * 2 shifts) 1 2 3 --> 3rd sort (1, 2, and 3 are shifted to allow all 3 characters to be shifted) (3 chars * 3 shifts)

I guess they simply don't deal with implementation in these videos.

Week 3, but not discussed in recent years!

@@davidjmalan Any particular reason for that?

So, how do you decide where to put the element at the new array? You still have to shift the existing elements inside the "new" array in order to add an element to it, which is basically the same if you only have one array.

I am confused as to why the selection sort is still n squared because for each iteration of the outer loop you will be reducing the size of the inner loop by one, and on top of this you still need to swap 2 items around on each iteration. For the insertion sort there is only one loop but its the swapping that seems to end up increasing the complexity, I wonder why this is not taken into consideration for some algorithms where they loop multiple times but also need to swap each time?

@@davidjmalan MVP