1
00:00:02,170 --> 00:00:09,670
So we derived how long this algorithm in the end takes in this Big O notation, where we basically only care

2
00:00:09,850 --> 00:00:14,810
about the dynamic parts in the algorithm and not about the constant parts,

3
00:00:14,860 --> 00:00:18,520
let's do the same thing for our second solution now.

4
00:00:18,580 --> 00:00:24,550
Now again here, we have a constant part, that's this if check, it only runs once and the same for the

5
00:00:24,550 --> 00:00:25,570
return statement.

6
00:00:25,570 --> 00:00:28,290
Now we learned that we therefore don't have to care about that,

7
00:00:28,330 --> 00:00:34,210
let's instead focus on the loop because that's the part that really depends on the array length.

8
00:00:34,210 --> 00:00:42,280
Now here we see we go through all items in numbers and then in there, we also go through all items in

9
00:00:42,280 --> 00:00:42,900
numbers

10
00:00:42,940 --> 00:00:50,530
in the end. Yes we start one item above the first one, so it's not the entire array we go through but

11
00:00:50,530 --> 00:00:52,080
again n-1

12
00:00:52,090 --> 00:00:58,390
but as I explained before, for large arrays, this -1 won't make a difference.

13
00:00:58,390 --> 00:01:01,980
So in the end we could say inside the first for loop,

14
00:01:02,050 --> 00:01:10,240
so this line for example will execute n times, if we feed in an array with 1000 items, we'll execute

15
00:01:10,240 --> 00:01:17,380
this line 1000 times because we go through all the items and then and that's the thing, inside of this

16
00:01:17,380 --> 00:01:19,540
loop, for every item,

17
00:01:19,600 --> 00:01:24,630
so for every n time, we go through the array again.

18
00:01:24,730 --> 00:01:28,460
So this executes n times as well in the end,

19
00:01:28,480 --> 00:01:33,610
we again go through the entire array but we do this inside of the outer array.

20
00:01:33,760 --> 00:01:36,090
So what's our total time

21
00:01:36,100 --> 00:01:45,710
this algorithm will then take? What's the time complexity here? Well the time complexity here in the end

22
00:01:45,710 --> 00:01:54,980
is n*n*n because we go through the outer array and then for every item, so n times,

23
00:01:55,190 --> 00:01:56,770
we go through the array again,

24
00:01:56,810 --> 00:02:05,540
so we have n*n and therefore this would be Big O n squared. So this simply means for one item,

25
00:02:05,550 --> 00:02:12,210
we of course only take one operation, if we feed in an array with one item, we take one operation

26
00:02:12,300 --> 00:02:19,860
but if we feed in an array of 1000 items, we in the end have 1000 times 1000 of different operations we

27
00:02:19,860 --> 00:02:23,750
have to execute, so a million and that of course is a lot

28
00:02:23,820 --> 00:02:30,360
and that's not growing in a linear way where for 1000 items, it takes 1000 times as long

29
00:02:30,360 --> 00:02:31,030
but instead

30
00:02:31,050 --> 00:02:35,340
that's a quadratic time complexity here. For 1000 items,

31
00:02:35,340 --> 00:02:39,900
it does not take 1000 times as long but a million times as long.

32
00:02:39,900 --> 00:02:45,450
So therefore if we compare these two algorithms, these two solutions where we have a linear time complexity

33
00:02:45,870 --> 00:02:51,380
and a quadratic time complexity,

34
00:02:51,600 --> 00:02:53,760
of course the linear one is better,

35
00:02:53,790 --> 00:02:56,040
this will take way less time.

36
00:02:56,040 --> 00:02:59,420
This algorithm here grows in a linear time,

37
00:02:59,430 --> 00:03:06,930
so for a million items, we take a million times as long as for one item whereas this grows in a quadratic

38
00:03:06,930 --> 00:03:12,780
way, which means for a million items we'll take a million times a million times as long as we do for one

39
00:03:12,780 --> 00:03:13,540
item.

40
00:03:13,560 --> 00:03:19,470
So if we have these two alternatives and we don't need to sort for any other reason, we should definitely

41
00:03:19,470 --> 00:03:24,620
go with this first algorithm here because it takes less time,

42
00:03:24,690 --> 00:03:32,730
it has o(n) instead of o(n squared) and that's how we compare algorithms and why this Big O notation

43
00:03:32,730 --> 00:03:33,650
matters to us.