1
00:00:06,460 --> 00:00:10,300
So now we're going to talk about theoretical evaluation.

2
00:00:10,690 --> 00:00:17,290
So remember, big O, there's two things that we need to keep in mind.

3
00:00:20,690 --> 00:00:27,020
The first being we do not care about coefficients

4
00:00:29,330 --> 00:00:32,540
and we will abbreviate that as co f.

5
00:00:32,690 --> 00:00:38,600
And the second thing is we only care about the highest power.

6
00:00:43,530 --> 00:00:43,870
Right.

7
00:00:43,870 --> 00:00:51,310
So now let's let's look at some examples of this and how we might be able to evaluate this.

8
00:00:51,880 --> 00:00:53,560
So let's say we have a vector.

9
00:00:57,060 --> 00:00:59,840
And let's put some values in here.

10
00:00:59,850 --> 00:01:06,270
We'll go five, three, six, one and eight.

11
00:01:06,780 --> 00:01:12,000
And for our first algorithm, we want to find the largest number.

12
00:01:14,520 --> 00:01:16,470
The largest number.

13
00:01:17,160 --> 00:01:17,760
Right.

14
00:01:18,510 --> 00:01:23,480
So you look at this and you say, okay, well, that's that's pretty easy to do.

15
00:01:23,490 --> 00:01:32,580
All we need is a simple for loop, you know, for X in the vector.

16
00:01:35,600 --> 00:01:42,230
Find the highest and that we can do that using a simple if statement.

17
00:01:42,230 --> 00:01:42,770
Right.

18
00:01:43,220 --> 00:01:48,560
So for this iteration right here, this is going to be an iteration.

19
00:01:49,850 --> 00:01:54,230
We know that X is going to be the value in here.

20
00:01:54,380 --> 00:01:54,770
Right.

21
00:01:54,770 --> 00:01:59,100
So that's how many times we're going to go through and for X in vector.

22
00:01:59,120 --> 00:02:07,760
Well, this is going to be the length of our vector.

23
00:02:09,560 --> 00:02:13,130
So this correlates to in.

24
00:02:14,180 --> 00:02:18,830
For how many items we have.

25
00:02:19,250 --> 00:02:19,640
Right.

26
00:02:19,640 --> 00:02:23,750
And so by doing this, find the highest logic down here.

27
00:02:23,750 --> 00:02:29,840
Inside of this iteration, we can logically conclude since we're only having to iterate through the

28
00:02:29,840 --> 00:02:36,590
vector one time that our big o notation is going to be o of n.

29
00:02:37,790 --> 00:02:39,380
And why is it o of n?

30
00:02:39,380 --> 00:02:44,720
Because we're only going through the vector one time, right?

31
00:02:44,990 --> 00:02:48,650
So now let's look at a slightly different example.

32
00:02:48,650 --> 00:02:51,710
Let's say we want to sort.

33
00:02:53,610 --> 00:02:55,200
The vector, Right?

34
00:02:55,500 --> 00:03:07,170
So for this, we'll do another four loop and we'll say four I equals zero is less than or equal to n

35
00:03:07,170 --> 00:03:10,680
plus one I plus plus.

36
00:03:10,980 --> 00:03:11,340
Right.

37
00:03:11,340 --> 00:03:15,420
So that right here alone again is the same as above.

38
00:03:15,420 --> 00:03:24,990
And that is o of n For us to sort it, we need to be able to compare and swap values in here.

39
00:03:24,990 --> 00:03:33,000
So we need to have our index here for I and then we're also going to need another for loop and we'll

40
00:03:33,000 --> 00:03:40,800
say it is J and we'll start J at one, right, because we want to be able to compare I and J.

41
00:03:41,100 --> 00:03:51,420
So then we'll say J is less than or equal to n j plus plus, and we'll say our big notation here, let

42
00:03:51,420 --> 00:03:55,470
me clean that up is o of an as well.

43
00:03:56,580 --> 00:04:04,440
And these are nested right because we have o of in here and then we have another for loop below it,

44
00:04:04,740 --> 00:04:11,310
which is also being executed every time that this for loop gets ran right here.

45
00:04:12,810 --> 00:04:15,600
So we have our nested for loops.

46
00:04:15,600 --> 00:04:18,270
We do our compare and swaps.

47
00:04:19,950 --> 00:04:21,330
Sort the vector out.

48
00:04:22,500 --> 00:04:29,790
And with this being a four loop, and then we have our open bracket, and then we have our other four

49
00:04:29,790 --> 00:04:31,350
loop right here.

50
00:04:31,350 --> 00:04:41,190
And let's label these bracket A bracket B Well, we close bracket B here and then we close bracket A

51
00:04:41,190 --> 00:04:41,730
there.

52
00:04:42,510 --> 00:04:50,940
And what happens with this is that for every iteration in in this A for loop, we're going to iterate

53
00:04:51,000 --> 00:04:54,240
through this loop as well, right?

54
00:04:54,240 --> 00:04:56,010
So I just want to make that really clear.

55
00:04:56,280 --> 00:05:05,280
And with that, we're, we're going to iterate in twice, right?

56
00:05:05,640 --> 00:05:10,140
And with that means that we're going to have an exponent of two.

57
00:05:12,070 --> 00:05:13,000
Our highest power.

58
00:05:13,000 --> 00:05:14,500
Yes, is two.

59
00:05:15,070 --> 00:05:21,550
So our big notation for this would be quadratic, as we showed in the experimental.

60
00:05:21,820 --> 00:05:23,530
And then our one up here.

61
00:05:23,560 --> 00:05:29,770
This is linear, so obviously O of n is more performant than o of n squared.

62
00:05:30,700 --> 00:05:37,750
And then if for some reason we had another for loop, so if we added another.

63
00:05:39,540 --> 00:05:40,680
Nested loop.

64
00:05:42,720 --> 00:05:43,680
For loop.

65
00:05:44,840 --> 00:05:46,610
Now, our big rotation would be.

66
00:05:46,610 --> 00:05:47,210
Oh.

67
00:05:49,380 --> 00:05:50,730
Then cubed.

68
00:05:51,090 --> 00:05:51,690
Right.

69
00:05:51,870 --> 00:05:58,350
So hopefully that makes sense because theoretical is a lot more.

70
00:05:59,850 --> 00:06:03,450
Time consider it when you're trying to evaluate your algorithm.

71
00:06:03,570 --> 00:06:10,890
And I wanted to talk about big notation early on in this course is the first thing, because as we go

72
00:06:10,890 --> 00:06:17,100
through and look at all these different algorithms and data structures, I want you to be familiar with

73
00:06:17,100 --> 00:06:21,510
what the big notation of that algorithm or data structure could be.

74
00:06:21,510 --> 00:06:28,830
And I want you to try and compute the big notations for some of these algorithms and data structures

75
00:06:28,830 --> 00:06:34,620
as we go through this course so that you're able to evaluate their performance and maybe you can even

76
00:06:34,620 --> 00:06:39,990
enhance them to improve their space and time complexity.

77
00:06:39,990 --> 00:06:44,310
So it's really important that we really understand what bingo notation is.

78
00:06:44,310 --> 00:06:50,040
So if you have any questions about it, please ask them and the Q&A section before continuing on in

79
00:06:50,040 --> 00:06:54,510
this course, because I really want it to be clear as to.

80
00:06:55,860 --> 00:06:59,610
How you can compute the big O notation of an algorithm.