Design And Analysis of Algorithm | Lecture2 | Faraz Khan — Transcript

Full transcript

1. 0:00in today's lecture we will discuss the
2. 0:02cases of algorithm
3. 0:04We have basically four cases of
4. 0:07algorithm number one is test case
5. 0:13now what is best case
6. 0:16suppose we have an array of size n equal
7. 0:20to 50.
8. 0:22and there is a key element which will be
9. 0:25going to find
10. 0:27or we have to find in that specific area
11. 0:33so as you can see that
12. 0:36the best case would be
13. 0:39while searching the key element of an
14. 0:42array
15. 0:44best case is the case when we find the
16. 0:48key element
17. 0:50at first location
18. 0:54or the first index of an array
19. 0:57example
20. 1:00we have an array of size n equal to 50.
21. 1:05and the key element key element is the
22. 1:08element which we are going to find
23. 1:12in a given area
24. 1:14so if we find that special element which
25. 1:17is 10 the key element which is 10 so if
26. 1:21we find that key element
27. 1:23throughs ABC algorithm we will call it
28. 1:28it's a best case
29. 1:30right
30. 1:31so whenever we find a key element at the
31. 1:35very first index we will call it a test
32. 1:38case right
33. 1:41the second one
34. 1:45second one worst case
35. 1:49what is worst case while searching the
36. 1:52key element of an array worst case is
37. 1:55the case when we find the key element at
38. 1:59last location of an array
39. 2:02what does that mean let me elaborate it
40. 2:05for example
41. 2:09we have a same array
42. 2:12of size n equal to 50 and the element we
43. 2:16are going to find in that array is again
44. 2:2010. so now you can see that if we find
45. 2:24that element
46. 2:27at the very last index of an array we
47. 2:31will call it a worst case
48. 2:34worst case scenario if we find at first
49. 2:37index we will call it a best case
50. 2:39scenario and if we find it
51. 2:42at the last index we call it a worst
52. 2:45case got it
53. 2:47let's move on
54. 2:53the third one is
55. 2:57while selecting the key element of an
56. 2:59array average case is the case when we
57. 3:03find the key element in between
58. 3:06second and second last location or index
59. 3:10of an error
60. 3:12what does that mean let me elaborate it
61. 3:15for example we have a same array of size
62. 3:18n equal to 50
63. 3:20and the key element we are going to find
64. 3:22is 10 just like previous two examples
65. 3:27same array
66. 3:29find that element here you can see that
67. 3:31see the mouse closely
68. 3:33this is index number
69. 3:36second
70. 3:37and this is you can see the movement of
71. 3:40the mouse this is the second last index
72. 3:45of an array
73. 3:47so if we find an element
74. 3:50in between second
75. 3:52and second last index or location of an
76. 3:56array we will call it average case
77. 4:01I hope you have understood let's move on
78. 4:06now asymptotic case
79. 4:10asymptotic case
80. 4:13asymptotic notations was developed to
81. 4:16provide the universal way to measure the
82. 4:19speed and efficiency of an algorithm
83. 4:23asymptotic algorithm precisely refers
84. 4:26for large input we measure the behavior
85. 4:29of algorithm when input size reaches
86. 4:33Infinity
87. 4:35what does that mean it means whenever we
88. 4:38want to analyze the large data we want
89. 4:41to analyze the infinite data so we would
90. 4:45rather prefer asymptotic notations
91. 4:49got it
92. 4:50so here we have three different
93. 4:53asymptotic notations
94. 4:56the first one is
95. 4:58Big O N
96. 5:02we call it a big O
97. 5:06and it's a upper bound
98. 5:11what does that mean
99. 5:14it means whenever we find the key
100. 5:19element
101. 5:21in a given array
102. 5:23at
103. 5:26the very last index
104. 5:29so we will call it a
105. 5:32upper bound
106. 5:34Big O and the complexity would be o n
107. 5:38Square in asymptotic notation
108. 5:41I repeat for example we have a given
109. 5:44array and if we find a key element at
110. 5:48the very last index of an array we will
111. 5:51call it a upper bound
112. 5:54and its complexity would be o n Square
113. 5:58right
114. 6:02let's move on to the end
115. 6:06we call it a Theta
116. 6:14what is the Theta
117. 6:16V represent Theta for
118. 6:19tight bound what does that mean
119. 6:24for example n is less than 3 n
120. 6:28and 3n is less than 5.
121. 6:31so n would be the lower bound 5 n would
122. 6:36be the upper bound and 3n would be the
123. 6:40tide bound
124. 6:42right so
125. 6:45we can even say that we can represent
126. 6:48the average case with the help of a
127. 6:50Theta n in asymptotic notations i o you
128. 6:54have understood
129. 6:58here is w n
130. 7:03you can see that w n
131. 7:05or Omega n
132. 7:08we call it Omega
133. 7:11and it represents a lower bound
134. 7:15so whenever we
135. 7:18find the key element at the very first
136. 7:22index of an array
137. 7:25so we will call it
138. 7:27lower bound
139. 7:29in asymptotic notation
140. 7:32and V represents lower bound with
141. 7:36Omega n or
142. 7:39T down
143. 7:43I hope you have understood
144. 7:47so at the end if we conclude
145. 7:51the asymptotic notations
146. 7:54while finding the
147. 7:56efficiency of algorithm we are always
148. 7:59interested in worst case which means for
149. 8:03analyzing the complexity of algorithm we
150. 8:06only care about the highest power and
151. 8:08ignore the rest
152. 8:10that is why for example we have a given
153. 8:14expression n k power 5
154. 8:17and having power 5 plus 4 n Cube plus 3
155. 8:21n plus five so the ultimate complexity
156. 8:24of the above expression is
157. 8:26and five
158. 8:28right
159. 8:29because one thing is damn sure but we
160. 8:33have discussed in lecture number one
161. 8:35whenever we find the complexity of an
162. 8:39algorithm
163. 8:40we are always interested in the worst
164. 8:43case
165. 8:44and
166. 8:46that is the reason whenever we have an
167. 8:49expression whenever we have a complexity
168. 8:51in the form of expression just like this
169. 8:56so we only care about the highest power
170. 8:59why
171. 9:00the simple answer is the highest power
172. 9:04represents the worst case and whenever
173. 9:08we find the complexity of algorithm we
174. 9:10are always always interested in the
175. 9:13worst case because worst case represents
176. 9:18the whole area
177. 9:20worst case represents the highest power
178. 9:24in worst case we go for the maximum
179. 9:29computational steps
180. 9:31right so with this I conclude lecture
181. 9:35number two