1
00:00:00,420 --> 00:00:08,700
‫So I want to touch on the big oh of insertion sort obviously because it has a for loop inside of a for

2
00:00:08,700 --> 00:00:10,740
‫loop it is o of n squared.

3
00:00:11,070 --> 00:00:12,600
‫That's for its worst case.

4
00:00:12,600 --> 00:00:15,960
‫That is the true big o of this would be o of n squared.

5
00:00:15,960 --> 00:00:20,190
‫But let's look at a situation where something is almost sorted.

6
00:00:20,610 --> 00:00:26,070
‫We're going to start here and we don't do anything else because the item before it is less than we put

7
00:00:26,070 --> 00:00:26,880
‫that back.

8
00:00:27,720 --> 00:00:30,480
‫And this one everything before it is less than.

9
00:00:30,480 --> 00:00:31,620
‫So we're not going to do anything.

10
00:00:31,620 --> 00:00:36,060
‫And this one, we're just going to move it over one and drop this in.

11
00:00:36,990 --> 00:00:38,580
‫And then we go to the next one.

12
00:00:39,900 --> 00:00:43,680
‫And then we keep going through to the end of the array.

13
00:00:44,220 --> 00:00:47,970
‫And you can see that we basically just made one pass.

14
00:00:48,850 --> 00:00:52,930
‫This would be in complexity, not in squared.

15
00:00:53,500 --> 00:00:58,120
‫And I wanted to point this out because the next couple of sorting algorithms are much more efficient.

16
00:00:58,120 --> 00:00:59,950
‫They are o of n times.

17
00:00:59,950 --> 00:01:00,790
‫Log in.

18
00:01:01,210 --> 00:01:04,750
‫They're more complex to write, but they are faster.

19
00:01:05,390 --> 00:01:10,670
‫But they're not going to be faster if you have almost sorted data.

20
00:01:11,180 --> 00:01:16,730
‫You can use one of these sorting algorithms that are more primitive, like insertion sort.

21
00:01:17,420 --> 00:01:21,980
‫That is o of in squared typically and have it actually run faster.

22
00:01:22,250 --> 00:01:27,680
‫So I just want to touch on this aspect of the insertion sort.

23
00:01:28,100 --> 00:01:28,880
‫Big O.