1
00:00:00,800 --> 00:00:02,660
Analyzing the algorithm.

2
00:00:02,660 --> 00:00:09,330
So to create a good algorithm, we need to ensure that we have got the best performance from the algorithm.

3
00:00:09,350 --> 00:00:16,580
In this lecture, we are going to discuss the ways we can analyze the time and complexity of basing

4
00:00:16,580 --> 00:00:17,390
functions.

5
00:00:17,390 --> 00:00:20,330
So my name is Stephan and let's get started.

6
00:00:32,000 --> 00:00:32,750
So.

7
00:00:34,270 --> 00:00:37,570
Uh, we're going to start with the asymptotic analysis.

8
00:00:37,570 --> 00:00:42,610
So let's start with the simplistic analysis to find out the complexity of the algorithms.

9
00:00:42,610 --> 00:00:47,410
So this analysis omits the constants and the least significant parts.

10
00:00:47,420 --> 00:00:55,450
Suppose we have the function that will print a number from zero, from zero to N.

11
00:00:57,550 --> 00:00:59,230
We're going to create a function like this.

12
00:00:59,230 --> 00:01:06,280
So void, void, or actually, let's make this here, the void looping here.

13
00:01:06,280 --> 00:01:11,200
We're going to get an parameter which is going to be n here and we will loop through it.

14
00:01:11,200 --> 00:01:14,380
So integer, we're going to create a new integer E here.

15
00:01:14,380 --> 00:01:15,970
We're going to assign it to zero.

16
00:01:16,000 --> 00:01:26,440
Now we're going to create a while loop while E is less than n print on the screen with a c out E here,

17
00:01:26,440 --> 00:01:27,550
end line.

18
00:01:28,120 --> 00:01:29,170
And here.

19
00:01:29,170 --> 00:01:31,570
We also need to input your string here.

20
00:01:31,570 --> 00:01:32,110
Oops.

21
00:01:32,740 --> 00:01:38,150
So include and include your stream, your stream.

22
00:01:38,270 --> 00:01:45,290
And so we're going to print it on the screen and increment the E by one.

23
00:01:46,340 --> 00:01:49,700
E equals E plus one.

24
00:01:50,000 --> 00:01:57,830
So now let's calculate the time and complexity of the preceding algorithm by counting the each instruction

25
00:01:57,830 --> 00:01:59,600
of the function here.

26
00:02:00,040 --> 00:02:07,450
So this statement is only executed once in the function, so its value is one.

27
00:02:07,450 --> 00:02:14,050
So this code snippet here of the of the rest statements in the looping function.

28
00:02:14,050 --> 00:02:18,280
So the comparison while loop is valued at one.

29
00:02:18,280 --> 00:02:25,390
And for simplicity we can say that the value of the two statements inside the while loop scope is three

30
00:02:25,420 --> 00:02:25,960
signs.

31
00:02:25,960 --> 00:02:35,590
It needs one to print the variable and two for assignment and addition here.

32
00:02:35,710 --> 00:02:42,970
So however, how much of the this code is executed depends on the value of N here.

33
00:02:43,150 --> 00:02:45,520
So it will be one here.

34
00:02:45,850 --> 00:02:59,870
Let's actually make our mathematical here so it will be one plus three and multiply by N or for n here.

35
00:02:59,870 --> 00:03:01,850
You can also do it like that.

36
00:03:01,850 --> 00:03:04,250
So the total instruction.

37
00:03:06,010 --> 00:03:13,480
Uh, that has to be executed for this looping function is one plus four.

38
00:03:13,480 --> 00:03:19,670
N Therefore, the complexity of this looping function is here.

39
00:03:19,690 --> 00:03:22,420
So the time complexity here.

40
00:03:23,150 --> 00:03:24,020
The time.

41
00:03:24,020 --> 00:03:25,070
Complexity.

42
00:03:25,100 --> 00:03:25,940
Time.

43
00:03:25,940 --> 00:03:27,200
Complexity.

44
00:03:27,260 --> 00:03:27,770
Yeah.

45
00:03:27,800 --> 00:03:28,490
Time.

46
00:03:28,490 --> 00:03:29,570
Complexity.

47
00:03:32,200 --> 00:03:34,590
And here time comes complexity.

48
00:03:34,600 --> 00:03:38,650
N is equals for.

49
00:03:39,360 --> 00:03:41,970
And plus one here.

50
00:03:41,970 --> 00:03:45,570
So and there is let's actually create our curve here.

51
00:03:45,570 --> 00:03:47,240
So in this case, it's our curve.

52
00:03:47,250 --> 00:03:55,020
For example, let's just create a score here and this is our way, this goes here.

53
00:03:55,590 --> 00:04:00,360
So it will be for N plus.

54
00:04:01,280 --> 00:04:01,970
One.

55
00:04:03,660 --> 00:04:13,050
So in our core graphics that will be represented in this course, the here, let's actually create this

56
00:04:13,080 --> 00:04:13,890
again.

57
00:04:17,270 --> 00:04:21,510
And this goes from here to here.

58
00:04:21,530 --> 00:04:25,850
So for n plus one.

59
00:04:27,790 --> 00:04:30,040
So this is the input axis.

60
00:04:30,040 --> 00:04:39,940
The x axis here represent the input size N and the U here, the x axis here.

61
00:04:40,260 --> 00:04:42,000
Let's actually write in red.

62
00:04:42,010 --> 00:04:46,030
This is U here and this is X here.

63
00:04:46,270 --> 00:04:53,430
So this axis here represents the execution time.

64
00:04:53,440 --> 00:04:55,570
So here this means here.

65
00:04:55,570 --> 00:04:58,630
This is the time.

66
00:05:00,050 --> 00:05:04,580
So as you can see in this graphic, the curve is linear.

67
00:05:04,580 --> 00:05:10,820
However, since the complexity is also depends on the other parameters such as hardware specification,

68
00:05:10,820 --> 00:05:17,300
we may have another complexity for the preceding looping function if we run the function on a faster

69
00:05:17,300 --> 00:05:18,050
hardware.

70
00:05:18,050 --> 00:05:31,130
So let's say that complexity becomes two N, let's actually here, yeah, two N plus 0.5 so that the

71
00:05:31,130 --> 00:05:34,520
curve curve will be like this.

72
00:05:34,520 --> 00:05:41,510
So for example, this was the previous curve and this is the this is going to be our next curve here.

73
00:05:41,510 --> 00:05:42,530
It's going to be like this.

74
00:05:42,530 --> 00:05:53,330
So this is the four plus four N plus one, and this is the two N plus 0.5 here.

75
00:05:53,330 --> 00:05:59,480
So it will be go down the time complexity if we have higher, faster hardware.

76
00:05:59,480 --> 00:06:04,260
So as you can see, the curve is still linear for the two complexities.

77
00:06:04,260 --> 00:06:09,990
For this reason, we can omit a constant and the least significant part is asymptotic analysis.

78
00:06:09,990 --> 00:06:16,500
So we can say that this complexity is n here.

79
00:06:16,500 --> 00:06:21,360
For example, the time complexity n here is equals to n.

80
00:06:24,510 --> 00:06:25,110
Here.

81
00:06:25,560 --> 00:06:27,870
So let's move another function.

82
00:06:28,950 --> 00:06:30,450
If we have nested while loop.

83
00:06:30,450 --> 00:06:32,460
So we will have another complexity here.

84
00:06:32,460 --> 00:06:34,860
So looping while and void.

85
00:06:36,230 --> 00:06:38,570
This is going to be my pairing here.

86
00:06:38,600 --> 00:06:41,540
Pair pairing here.

87
00:06:41,540 --> 00:06:50,810
And it's going to also get the integer n and we will create a new value named integer E here zero while

88
00:06:50,840 --> 00:06:53,810
the e is less than n.

89
00:06:54,820 --> 00:06:55,810
Then we're going to.

90
00:06:56,850 --> 00:06:57,860
Could a new value.

91
00:06:58,140 --> 00:07:01,140
The integer g here is zero.

92
00:07:01,320 --> 00:07:09,720
And while the g g is less than n, we will print this on the screen.

93
00:07:09,720 --> 00:07:12,180
So see out E here.

94
00:07:14,840 --> 00:07:19,100
And also here and in line and line.

95
00:07:19,670 --> 00:07:22,460
After that, we will equal G.

96
00:07:22,550 --> 00:07:24,470
Equals G plus one.

97
00:07:24,470 --> 00:07:31,310
And outside the our nested while loop in the first while loop here inside the first while loop we're

98
00:07:31,310 --> 00:07:34,340
going to equal E equals e plus one.

99
00:07:34,370 --> 00:07:35,390
E plus one.

100
00:07:35,960 --> 00:07:36,190
Yeah.

101
00:07:36,320 --> 00:07:43,250
So based on the looping function here, we can say that the complexity of the inner while loop of this

102
00:07:43,250 --> 00:07:48,650
parent function is for n plus one.

103
00:07:48,650 --> 00:07:50,840
So we then calculate the while loop.

104
00:07:50,840 --> 00:07:55,730
So it becomes uh, here, uh, let's actually make this like that.

105
00:07:57,760 --> 00:08:00,010
The one plus.

106
00:08:00,720 --> 00:08:07,500
And multiply by four n plus one and plus two.

107
00:08:07,740 --> 00:08:17,550
So which equals to one plus three N plus four N square here.

108
00:08:19,230 --> 00:08:20,100
Square.

109
00:08:20,400 --> 00:08:27,180
So therefore, the complexity of this preceding code is this.

110
00:08:28,130 --> 00:08:30,260
Time complexity is going to be.

111
00:08:32,590 --> 00:08:35,140
Here in this, as you can see here.

112
00:08:35,140 --> 00:08:44,380
So here the time complexity instead of for n plus one, we're going to have the for the time complex

113
00:08:44,380 --> 00:08:52,150
is going to be for n square here for n square plus three n plus one.

114
00:08:54,190 --> 00:08:59,620
So and the curve of this preceding flow is going to be like this here.

115
00:08:59,650 --> 00:09:07,810
This is our curve and it's going to be go from here and update like this.

116
00:09:07,870 --> 00:09:08,040
Oops.

117
00:09:08,050 --> 00:09:10,470
Actually, let's make the different color here.

118
00:09:10,480 --> 00:09:12,490
Go from here and update like this.

119
00:09:12,670 --> 00:09:24,010
So here, this is going to be for n for n two plus three, N plus one, and it's going to be this is

120
00:09:24,010 --> 00:09:27,020
the time and this is the complexity here.

121
00:09:27,040 --> 00:09:35,350
So and if the run if we run this code in the higher software, the complexity might become twice as

122
00:09:35,350 --> 00:09:35,620
slow.

123
00:09:35,620 --> 00:09:39,910
So and the notation is going to be, for example.

124
00:09:41,520 --> 00:09:43,220
Eight and square.

125
00:09:43,540 --> 00:09:44,310
Eight.

126
00:09:45,510 --> 00:09:50,220
Yeah, the notation is going to be eight and square here.

127
00:09:52,600 --> 00:09:54,910
Plus six and plus two.

128
00:09:54,940 --> 00:09:56,890
It's conversation is going to be like this.

129
00:09:57,700 --> 00:10:02,710
And the curve of notation is gonna like this.

130
00:10:02,710 --> 00:10:13,750
So, for example, let's say this is our previous curve and this is going to be our next curve here

131
00:10:13,750 --> 00:10:14,560
like this.

132
00:10:15,040 --> 00:10:22,150
And this is going to eight N square plus six and that we've written here plus two here.

133
00:10:22,150 --> 00:10:22,810
So.

134
00:10:23,710 --> 00:10:30,730
And as shown here, signs the asymptotic analysis omits the constant and the least significant parts.

135
00:10:30,760 --> 00:10:37,420
The complexity of the notation will be n two of our time complexity.