COMP2521 26T2 Week 1 Lecture 2

本站添加: 2026-06-06

[00:01:30]How is it?

[00:02:03]I don't know.

[00:02:48]This is short.

[00:03:31]Hello everyone.

[00:03:33]Is it working?

[00:03:35]>> No.

[00:05:34]This one.

[00:05:44]Hello. Now it's working. Okay. The other one not working.

[00:06:09]Okay. Hello everyone.

[00:06:12]Uh let's start the second topic. Before I explain about this one, do you have any question from last week? Last week? No, last session.

[00:06:30]No. All good.

[00:06:34]So just a quick recap.

[00:06:39]Last session we talked about recursion which is a type of repeating technique in your programming and we see that recursion is actually kind of calling the function from inside of the function and to do recursion we actually need extra memory because every call need to be saved somewhere which is uh stack call is a part of RAM.

[00:07:09]How big is this actually a size depends on the operate this operation system that we are using or compiler we are using or normally is it like a few megabytes because of that if you are using recursion we have to be careful that uh how what is the size of the data set and how many calls or program actually create otherwise we may see a stack overflow error because of be using all this uh stack memory that already reserved.

[00:07:44]So today we will talk about data analysis. It's very important topic recursion and this one we will continuously repeat throughout the term because in almost every topic uh we have this uh recursion and also check the uh actually the algorithm uh efficiency using this criteria that we will discuss today.

[00:08:14]So let's see why even we need uh to analyze an algorithm.

[00:08:22]Uh because as I mentioned yes um Tuesday we need to do programming like a computer scientist not just put the codes. We need to see that if the code that we are actually preparing or writing how good it is and how it behave with different input size which is very important for whatever uh coding or algorithm we can check two important things. one is the time or time complexity and another is space complexity for each algorithm or data structure that you are using. So and but today we will mostly focus on the time complexity. However, we see for example in recursion also space is important. You have to take care of how much space or data structure are already using and we will see this space feature in other data structures also that we will discuss later but uh we today we will mostly focus on the time. So how we can find actually time complexity of an algorithm.

[00:09:39]So we do this analysis because of important reasons.

[00:09:46]First is we we want to compare different solution. As I mentioned, we may have different type of sorting or different type of search but we want to see which one is better based on the data we are using. So we will see that there are really uh very different different methods and we have to care about which one we are choosing based on our data and also we can predict the performance uh and behavior of our code when we have a large input. This is very important because for a small input there is not that much differences between different search or sorting or any other type of algorithm but when we dealing with large data that's very important that which algorithm we are using and also this analysis is this is important this is machine independent comparison we are not caring about where later we want to run this algorithm.

[00:10:52]We just want to compare different algorithm based on their mechanism itself. Doesn't matter it will be run on multiple CPU, GPUs, on laptop or whatever.

[00:11:04]We want to see the performance of the algorithm itself regardless of the machine that we want to use for running the code. And also finally we want to have a better uh design decision based on the uh work that you are doing or data set that we have.

[00:11:25]Um now we see few examples that where time complexity is important and then I will explain in detail actually what is time complexity.

[00:11:39]uh just imagine we have some V programming for a high frequency trading which things change in microsconds. So here even uh how our code is running or how fast it is can affect the um the performance or in engineer um search engines that [clears throat] we have billions of pages. So our code is very matter that how deal with all this big data in real time systems in big data processing in mobile or web apps. So these are the examples that really time is important even microsconds can change things. So this is aware that we should care about the time complexity of our algorithm and about space. We know that now we have lots of memory available but still there are cases that maybe we have a limited memory available like mobile devices or embedded systems.

[00:12:45]uh again even we have a large memory when we are dealing with larger scale data still it can be a bottleneck so we should care about how much space our algorithm is using and also recursive algorithm that already we discussed that it needs memory and it's important that we check how much memory or program actually using otherwise we will see a stack overflow uh risk any question till Now nothing.

[00:13:20]Okay. Now let's focus on time complexity which is the important topic. The most important things here when I'm talking about time I'm not talking about second minutes and hour. We are not talking about like time as we know generally here time means how many steps or algorithm needs because if we want to focus on the real time like how many seconds needs to run our program then it will be depend on the machine that we want to run our program it is the CPU it's a GPU it's your own u actually laptop or whatever so regardless where we want to run. We want to see how many steps or operations this algorithm needs especially when we have a large input.

[00:14:17]Overall we call it time complexity but it's actually is not the time that we normally use is a number of steps or behavior of our algorithm when we have a large data set and in help as I mentioned we compare different algorithm and see which one is faster or need actually less steps to find what you are looking for and Um sometimes uh we have to choose that we want to have a more faster algorithm or space is more matter for us. That depends on the type of the problem that we want to work on it that we choose that uh we want to sacrifice which any of them or but in most cases time is more important. So we will try to find a solution that have the minimum steps or operation to finish the task.

[00:15:23]Uh to learn how we can find time complexity of piece of algorithm.

[00:15:31]Uh I just started counting. I will tell you what is exactly counting is and how you can count the number of steps of algorithm but this is not something that I ask you later for example in your final question I said count the number of steps of this algorithm I'm just showing you how we count because from counting we can find time complexity just to have some idea of which from where actually this ruler coming is coming from counting. So we will see some example of counting how we can count the number of steps exactly and then later when you become expert you don't need to count you just have a look to the code and then directly can say what is the complexity of this code. So we have a difference between counting and analysis. Contin is finding the number of steps uh exactly how many times this code actually run each line of it and um any question till now okay so let's see let us start with counting you want to I want to show a few example just uh one thing if you already download this slide I upate last night. So, please download the latest version. We're going to change it a little bit and add more uh actually examples into these slides. So, use make sure that you have the latest version.

[00:17:07]Let me have a look if any question and then we will continue.

[00:17:15]Okay.

[00:17:20]Okay. Let's see first example.

[00:17:23]Suppose we have a very small piece of code and we want to see how many steps need this code to be run.

[00:17:33]This is a a for loop and a print inside of the loop. In counting actually we will check each and every line and each and every operation and check how many times it run if you want to run this code. So for we have a two lines the four and then print f. So suppose n is whatever number you think how many times that four loop will run n times.

[00:18:10]>> I don't think so.

[00:18:20]It's n + one time. Why?

[00:18:26]End time the condition is correct and print will be run. But the last time we will check and the condition is not made. So it will stop running. Correct?

[00:18:37]So for line itself n + one time but the print inside of it end time. Any question on this or is clear?

[00:18:50]>> So >> yes.

[00:18:59]>> Yeah. I want to >> because we need to know these total steps. Then we will see how from these total steps we can find the time complexity. So I just want to show you a few examples.

[00:19:17]Let's see how can I if I can do here or I need to take it.

[00:19:37]So this line is n + one time and this line n. So total will be 2 n + 1 the number of steps that we need to run this code.

[00:19:54]Okay.

[00:20:00]How about this one?

[00:20:03]How many steps this one needs?

[00:20:09]X² >> N² >> uh but I need to uh number of steps complete it is n² the complexity but how many steps overall sorry n² so okay let's Okay. The outer >> loop n + one time correct. How about the inner one >> again? n + one is it correct?

[00:21:10]So what should be >> just n >> no >> sorry >> no just I'm talking about this line itself >> that we will see print f how many times will be wrong >> we know that when i is zero j will go from zero to n correct and then we back I will be one and then J again zero to N.

[00:21:46]So again and again again. So can I say n * n + one this n coming from outer uh actually loop and n + one is this one itself because n times this loop running and how about print Yes, correct or no?

[00:22:27]Y n multiply n.

[00:22:34]>> Sorry.

[00:22:39]times.

[00:22:41]>> Yeah, because the loop always we check one more extra n + one time but whatever is inside of the loop is one time less.

[00:22:51]So is n time itself. Since these two line are uh inside of the outer uh actually loop.

[00:23:02]So we will multiply by n.

[00:23:05]So overall how many steps? n + 1 + n2 + n + n2. So 2 n 2 + 2 n + 1.

[00:23:24]This is the number of steps. Oh, sorry.

[00:23:28]Please any question?

[00:23:40]Yes.

[00:23:44]>> Explain again. Okay.

[00:23:48]So you you uh agree that the outer for running n plus one time.

[00:23:56]Yes. So whatever is inside of that loop will run one time less. Okay. So the second loop and print f will be n but print f itself is inside of the second four also.

[00:24:16]So based on that so this outer layer is n + one time whatever is inside because of this outer four will run n time plus this four also is here which is n + one time now which part is like not clear for you any other question yes >> why doesn't the happen as a step >> sorry >> why doesn't the happen as a step Which one I j >> we actually when we counting the detail we can count each of these stems separately but I to simplify I'm just considering loop as a one together but if you want to go in detail then int i equal to zero is different operation condition is different operation and that's uh increasing Decreasing steps also different but to simplify it I'm just considering whole loop as one because both are correct.

[00:25:27]>> Yes.

[00:25:32]>> I will show you.

[00:25:33]>> Yeah.

[00:25:37]I'm just starting with easier one and then go for more complex.

[00:25:43]How about this one?

[00:25:49]This is not nested loop. The previous one we call it nested loop. This is two separate loop but one program.

[00:25:59]What is the number of steps here? I just want to make sure you understand this part because this time complexity is actually very important. If you learn now then you will be guaranteed that whole term you will not have any issue with this subject. Because of that I put different example just to show you.

[00:26:17]Please if you have any question just ask now Okay, here we have two independent for loop.

[00:27:12]This one how many times?

[00:27:15]>> n + one and this one end time. And this one n + one and this one end time. Because this loop is two separate loop this not nested. So the total will be 4 n + 2 number of steps.

[00:28:06]Now we will see example why how it works here or index for a step every time dividing by two.

[00:28:20]So it's not like previous examples that increasing by one or decreasing by one.

[00:28:24]You'll be dividing every time.

[00:29:06]What do you think about this one? Any idea?

[00:29:13]>> Yes.

[00:29:17]>> Sorry. [clears throat] >> Which one?

[00:29:25]>> Maybe.

[00:29:30]If you see something like this that you are not sure, you can just try it with a small n to see how many times each line is actually running. Like just put n5 and see how many times that while and the lines inside of the line uh while is actually repeating.

[00:29:57]Initialization is always one because we just one time initialize but whatever is important is this part the y one every time this index is dividing by two just let's show you like small example suppose n is five okay i is five here So I will be five. Here in the while loop it says if I which is five is more than one. Yes.

[00:30:40]Then I divide by two. So five 2. So I will be two and print will be run. Next time in I is two. If two is more than one.

[00:31:03]Yes. Again I will be 2 / by two which is 1 and print will be run. Next time I is one.

[00:31:17]So if one is more than one, no. And then finish.

[00:31:29]So because of the the I is every time dividing by two. So while loop itself and the lines inside of it just running actually log n times base 2.

[00:31:54]So if I say this line is one time this one log n + one that because we see we have a extra check you should check one more time to find out this condition is uh actually correct or no and whatever is inside of the file again log n log n so it will be 3 log n + two.

[00:32:24]Yes.

[00:32:29]>> Again.

[00:32:32]>> Yeah. Because every time that's uh counter or I dividing by two. So that's it's running log n base two times.

[00:32:44]>> So it's like exponential.

[00:32:47]>> Yes. given is I * 2 again it will be log >> so is it just log or is it log base two >> base two but mostly we ignore base >> but because it's dividing by two is actually base two if it was dividing by three will be base three >> okay >> yeah you can just draw face just put is correct Yeah, but then just put it so you know that because of the division of two and based on what you are dividing that base can change but more complicated you know the actual >> yeah actually for time complexity and just we just you will see you just have a look and then say the complexity directly you don't need to count in detail because that is the one of the problems I will mention that counting is not always possible because code can be very complicated and very difficult to count one by one but I'm just showing you counting then when you see complexity you know where it's come from but yes that's correct we cannot do for like complicated codes >> when we express you also like task to for this group.

[00:34:25]>> Yeah, that two coming from one is from the first line and one is from y.

[00:34:32]So that plus two coming from those two numbers. this one because this initialization just run one time and then always the y itself run one more time to check the uh condition and this is the last example then we will see how we can simplize this and don't need to all this is the last Yes.

[00:35:12]>> Yes.

[00:36:17]Okay, this one for itself n + one time and whatever is inside of the four will run n times. Correct? So all of this line has n already now. So this one end time. Now we have a while. We already see that while run log n + one time log n + one time. And whatever is inside of the vile is log n and again log n. So then you need to sum all this.

[00:37:07]So how many this will be n + 1 + n + n log n + n + n log n + n log n 3 n log n + 1 2 3 n + 1 So as you can see these are the like simple code it takes like is getting more complicated. So it's not common to count the exact number of steps. What we need is to know how this code behave when we give a big data as input.

[00:38:02]Any question here?

[00:38:06]Okay.

[00:38:12]Uh to simplify all this counting because we don't need all this detail. For example, just think for example this one if n is million if it's really matter this putting this one here.

[00:38:32]No, because we always want to check complexity in the worst case when the input data is very big. So looking all these detail when we have a very big data actually is uh not helpful because that's will not have that much effect on the total complexity of the code.

[00:38:53]So uh to simplify counting and then find what part of this actually containing uh dominate the rest we use theory we call it asic behavior. In ascent behavior we say actually an algorithm behaves when the input size become very large and also we ignore a small detail and focus on the growth trend. We have an example here. For example, if the number of counting is 2 n + 5, if n is a small like n is five, there is no that much difference between two n terms and five as a constant. But if n is large like 1 million, then that five actually um not dominant and the other part is dominant. So when we want to show the complexity of the code, we want to see which part is dominant just that is enough to say to say how uh complicated is a code.

[00:40:00]For example, look at this examples.

[00:40:04]Uh imagine we have some codes and we count the number of steps. Now we want to say actually what is behavior of this uh piece of code or algorithm. If we have a large input data uh when we want to simplify we always focus the larger part of this country and also we don't care about the constant numbers for example for the first one I will do one and then you can also do the rest for this one for The first one is 100 n + 12 n + n. For the large n actually what is important is n itself. So if I want to simplify we just say the behavior of this co this part of code is n base based of something uh behavior. How about this one? Which one is dominant?

[00:41:13]>> Just this. The rest is not actually important when the size of the input u data is large. How about this one?

[00:41:24]n log n. We just pick the largest term in this uh equation. How about this one?

[00:41:35]This one we always drop the constant.

[00:41:41]This one n is larger or log n.

[00:41:45]This one n square n.

[00:41:50]This one >> log n. This one any question?

[00:42:06]>> Yes.

[00:42:10]mediumsized programs would still >> No.

[00:42:15]>> Okay. Because we always uh check the worst case. We will say that if there really is a very large data uh we will see that actually is the next slide when we were analyzing algorithm we have a base case average case and worst case but what is we really care about is the worst case but I explain why worst case is important. So here when we are simplifying we just think about what is the worst case.

[00:42:53]Uh as I said when we analyzing algorithm uh we can check it in three different cases. The base case it means with minimum number of steps we can get the results that we are looking for. Average case in average how many steps this code needs. For example, if you are searching for something just imagine we are doing uh search and worst case what is the worst case to or the maximum number of steps a code need to get what we are looking for. Um best case and average case all of these actually depend on the input data.

[00:43:38]uh but we always care about worst case because we don't know that regarding the input data that we have even ever base case or average case happen. So when we are comparing different algorithm we will see uh worst case and in worst case which one is better not base or average case.

[00:44:02]And for base case normally we use the omega for average case theta notation and for worst case big O. But you can see in some uh resources for showing all three of these cases they just use big O including this course. If you see the rest of the slides whenever we talking about best case, average case or worst case we always put big O. The reason I put two other just if you see somewhere else you know that this is correct. They have a specific notation for each of these cases. But in some resources, they don't care about it and they put everywhere big O. We also will do the same. Yes.

[00:44:56]You don't have to just define all this particular condition that are working that is itself needs lots of work to find exact number of steps and then later you will see that finding complexity is not difficult that much.

[00:45:15]>> Yes.

[00:45:30]Uh yes actually we are looking in the worst case when we are getting more dominant part that is what you're asking that why we get the most dominant >> isn't it the best case because you're not including all >> no best case actually for example imagine you have the data and you want to um is already sorted and you are looking for a smaller item and you are doing linear search we will not check you with first check you will find what you are looking for so just with one search you find what you are looking for so this is the best case in the worst case is just random so you have to check each and every item to find what you are looking for so if best average worst case is depend on the input data if it's sorted not sorted is random or whatever based on what is the problem so now uh so from now on I will show all of them with big notation now uh let's see two examples uh linear search and binary search which is uh clearly We can show uh difference between algorithm that doing same thing and also we can see what is the best average and worst case in any of these cases. Linear search means um we want to find a particular item in array. For example, in your search, we will search one by one from beginning until end of the array to find out if the item that you are looking for actually exists in the array or not. We call it linear search.

[00:47:28]Uh, and here you can see the code. We start from first item until the last one. And as soon as we find the target uh this actually for loop will uh stop. And if we reach to the end of the array and we couldn't find the item has been return minus one which means that item is not exist in the array.

[00:47:58]Just imagine what we are looking for is the first item in the array then it will be the best case because we just run this for one time and then we could find what we are looking for. So the complexity is just 01.

[00:48:16]Uh just one thing is not because of we run it one time. We always if we run uh for a constant number like two times, five time 20 times we can do a task. We always show it with 01.

[00:48:36]And what is the average case? If we just search almost half of the array and then we find whatever we are looking for in this case we almost just check half of them and again we say the complexity is O the last part I will explain more later and the worst case is the item that you are looking is almost the last item or is not exist so we have to check each and every item in the array to see if it is exist in the array or not. This is the worst case that we have to check all the cases.

[00:49:19]Any question here for linear search?

[00:49:22]Yes.

[00:49:26]>> Yes.

[00:49:28]Big O the notation I said in the previous we have three different type of notation to show best case, average case, worst case, omega, teta, big O but as I said in this course and maybe in some other resources they show all three of them using big O. This is a notation that we use for showing time complexity of code.

[00:50:00]So is it clear for you here what is the best operator or worst case or no?

[00:50:06]>> Is it? Yes.

[00:50:07]>> So what if in addition to the if there's an if else or else? Do you count?

[00:50:18]>> Yeah, there's an if else. Sorry, an else linear search. Now every single branch.

[00:50:26]>> Yes.

[00:50:38]>> Linear search just take items from first to last. So there is no other else or other stuff. But if it code has more component then we have to have a look what the algorithm is doing and how it behave regarding the input data.

[00:50:56]But here this linear stretch is always like this.

[00:51:04]And from the code also you can say it is O correct because you just have one for loop which is the main steps coming from four which is n + one time running. We ignore the constant. So the n is dominant here. Correct.

[00:51:27]Yes.

[00:51:30]>> Oh, here. No, we don't because now uh I suppose you know that uh the main line here is for loop which in this condition train n + one time and we ignore the constant. So overall it is o n in the worst case. We don't need to see all the detail. Just check the loops.

[00:51:55]If I give you even a bigger code, you just see how many loops it has. If this is nested or they are separated and just just uh visually you can check the algorithm and find out how many times is right.

[00:52:14]>> Yeah, you better two nested or nested and also you have to check the steps also. It is increasing uh one by one, decreasing one by one or dividing or multiplying and based on that you can say it is n or log n or whatever just have a look the main part how many loops you have if they are nested or no and how the steps changing these are mostly affect the overall complexity of your algorithm.

[00:52:46]>> Yes. Is there anything?

[00:52:53]>> Yes, I will show you. Yeah, >> it can be everything mathematically meaningful.

[00:53:03]So in linear search doesn't matter the data is sorted or unsorted. will always check from first item until find the item or go to the last item and cannot find it.

[00:53:19]Uh very simple but it's not efficient when we have a large like million of uh item in array then you have to check one by one until end. So it's not efficient when the data is quite large.

[00:53:35]Any question about linear search?

[00:53:43]And now we see another way of searching which is binary search. And then we can have some understanding how different algorithm actually can uh affect in final uh performance of your code.

[00:54:00]The second method for searching item is binary search but it just work on sorted array. This is important. It should be ascending or descending sorted. We suppose in this course that if you are talking about binary search or we saying it is sorted it's sorted from uh smaller number to larger number it is ascended.

[00:54:25]So uh to start from lower smaller number now let's see how this algorithm work and then I will show few examples so you can understand better because is already sorted when we are looking for an item first we directly have a look to the middle item we should find the middle of the array if the item that you are looking is the middle one the search will be complete and finish otherwise we will compare the target with the middle item. If the target is smaller than the middle item we need to just check the first part of the array or left part of the array and if the item that we are looking for is larger than meat we just check the right uh side of the array. So every time we divide our search space to the half instead of looping items one by one every time we divide our search space to the half. So we don't need to check each item separately to find what we are looking for.

[00:55:42]Um this is the algorithm for binary search. Just imagine we have an array.

[00:55:50]The first index of the array we call here low and last index high. In some resources you can see left and right the same.

[00:56:01]Uh as long as the index of low is smaller than or equal than high. First we want uh we will find the middle of the array. If the middle item is uh the target that we are looking for then we return middle and the search will finish. Otherwise we will check that if target is less than middle item we have to search the first part of the array or left part. So we have to uh check change uh the index of the low otherwise we will search the other part of the algorithm array and this is just uh recursive algorithm but doing exactly the same uh as long as low is more than high uh if it's low more than high it means I mean the base case or uh stopping condition otherwise we will find the mid of the array and then again compare with target and if is needed we check the left part or right part of the uh actually uh array now let me show you the process using few examples then it will be more clear for you how is actually working any question here or I show you like example how it work.

[00:57:38]Okay, let's try this.

[00:57:55]Okay, we are looking for nine.

[00:57:58]Now we want to see how we can do it. First we have to check if this array is sorted or not. We can see that is already sorted. So we can apply u binary search otherwise binary search will not work.

[00:58:17]Um this is index first one two three four five and six. First thing um this is low and this is high and the condition is always low should be smaller than high otherwise that's the sub condition that you have to stop searching. So now low is because we just started low is zero, high is six. We have to calculate mid which is 0 + 6 / 2 which is three. So this is our mid item.

[00:59:09]We are looking for nine. So definitely mid item is not nine. But we know that 9 is larger than or greater than seven. So [clears throat] with just one step we actually know that we have to just search the right section of the array. So or search space became half. We don't need to check the other part at all because we are sure that what we are looking is in the right sorry. So in the next iteration now low will be mid + one because we are checking just this one. It seems we have just this array 9 11 30. So here is low and here is high. So low is mid + one.

[01:00:01]Mid was three. So 3 + 1 will be four and high is six. Again we calculate meat which will be five. So this one index was let's put different color. This index is four five six. Now mid is this item.

[01:00:27]So definitely this is not nine but 9 is smaller than 11. Again we just need to check left part.

[01:00:40]So here we are taking left part low is 4 high is mid - 1 which is 5 - 1 4. So the mid will be 4 + 4 / 2 4. So now we check item four and we found what we were looking for just in three steps instead of checking item one by one.

[01:01:20]Any question?

[01:01:35]>> Yes.

[01:01:40]>> Four.

[01:01:44]>> Yeah. Yeah. It doesn't matter because if you want >> you always check the floor when you divide.

[01:01:52]>> Okay.

[01:01:52]>> Yeah. So >> the even or odd >> but is there a scenario where this happens and it is >> no >> it cannot miss it.

[01:02:11]What if the number appears twice in the >> number doesn't exist?

[01:02:18]>> Twice. Uh normally we say no repetition but if it is twice it can find it. The the for example if there is multiple as soon as find one sample of that number the the search will finish. You will not care about is there any other more or no.

[01:02:40]Yes.

[01:02:40]>> Is there a way to program it so that >> yes, you you should change it. You if you find it then you shouldn't uh like return and break the loop. If you want to continue then you will actually because you finding all the possible repetition then you are actually breaking that binary search rule and using more steps than the original version is used. What is possible?

[01:03:22]>> Okay, let's see another example.

[01:03:46]Okay, another example again it should be sorted and we will start again uh index 0 1 2 3 4 5 6 7 8. So low is 0, high is 8, mid will be 0 + 8 / 2 which is 4.

[01:04:16]We found the mid item which is 17 and we are looking for 23. So we need to just have a look to the right side of the array. So our search space became half.

[01:04:33]Now we have to have a look just this far.

[01:04:38]So low will be mid + one which is 4 + 1 5 and high is still eight. And again we have to find mid which is 5 + 8 / by 2.

[01:05:00]um will be six.

[01:05:10]So next me is this item this one.

[01:05:16]But again we didn't find 23 and we know that 23 is larger than 19. So again we have to have a loop to the right part of the remaining array. So next time we just searching this part.

[01:05:37]Low again will be mid + 1 which is 6 + 1 7.

[01:05:46]High is 8 and mid will be which is seven.

[01:06:12]Still what we are looking we didn't find it and we know that 23 is larger than 21. So we have to have a look again the right side of the array here. Low will be mid + 1 which is 8.

[01:06:35]High is 8. So mid will be 8 + 8 / by 2 eight. We check and we found it. Finish.

[01:06:46]So in four steps we could find the number that we were looking for.

[01:06:54]Any question?

[01:06:57]>> Yes.

[01:07:05]>> Sorry.

[01:07:10]>> 7 + 15 >> divide by two. [clears throat] seven and a half you always get the flow.

[01:07:20]>> Yeah, because sometimes there is odd number, sometimes is a even number.

[01:07:24]Always divide and get the flow.

[01:07:29]And the last example to finish this.

[01:07:34]Okay, this one.

[01:07:53]Okay, this one we know that it's not exist but we have to see how actually by research find out that this item actually is not exist in the array. The array is already sorted and we are looking for item two.

[01:08:12]Again this is 0 1 2 3 4 5 and 6.

[01:08:20]Low is zero.

[01:08:23]High is 6 and mid is 0 + 6 / 2 which will be 3. So this is the middle item.

[01:08:35]Uh we didn't find two and we know that two is smaller than 19. So we just search the first half of the array. This one.

[01:08:46]Now low is again zero and high is mid - one which is 2 and mid is 0 + 2 / 2 which is 1.

[01:09:04]We have a loop to item one. Again we didn't find two and we know that two is smaller than six. So we have to have a look again this part here. Low is zero and high is mid - one which is 1 - 1 which is 0. So mid will be 0 + 0 2 which is 0. We have a look to the zero item.

[01:09:41]Still we didn't find.

[01:09:44]So we know that two is actually smaller than three. So it try to go again to the left to find the item. [clears throat] So it says low is mid sorry low is zero and high is mid minus one which is 0 - one - one. Now there is a condition here low become more than high. So this is a stopping criteria. So it means the item is not exist and the binary search will stop.

[01:10:31]So we checking the low and high index.

[01:10:34]If low become more than high then it will stop.

[01:10:49]This is another example just show how it works. Always we check middle item. If we looking for something smaller than 11, we have to go to the left. If we're looking for something larger than 11, we have a look to the right. Again uh we find the if for example what we are looking is uh in the left side again we find the middle and then have a look to the left again right. So this is continue until either we find the item or we meet the stopping criteria and the search will stop.

[01:11:26]Um best case here if uh the item the target that we are looking for actually is the middle one.

[01:11:36]So just we finding first middle we find the item. So it will be best case an average case uh and worst case are the same and it is log n because every time we have to search a space. So because of that this is law and the difference is as I said when the input data is quite large for example if I has a million item and you are looking for item if you do if you use linear search you need million time check items one by one if you're using binary search in 20 steps you can find it. So as I said this difference between algorithm doesn't make sense when you have a large input data. Now you can see how different acting these two uh actually search.

[01:12:37]Yes.

[01:12:49]>> So it will not be binary search. it will be again sorted then there will be I don't know how we can call it >> so but that will be even more complex because then you have to have three searches space to have a look but it's possible to implement it that way regarding your data less steps like the number >> I'm not sure I have to see how it works in the large data but because every time you are finding two mean and more comparison probably even more steps.

[01:13:23]>> Okay.

[01:13:24]>> Because the number of check you are doing even more.

[01:13:27]>> Okay. Thank you.

[01:13:29]>> I'm not 100% sure but it is it will be more.

[01:13:32]>> Thank you.

[01:13:34]>> Do you need break?

[01:13:37]>> Yeah. You can have just quick five minutes break and then we will continue the last part.

[01:22:46]Are you ready?

[01:22:59]Yeah.

[01:23:20]>> Okay.

[01:23:21]This is question.

[01:23:27]Why is it fun for other cases big old?

[01:23:32]Because as I said in uh some resources we always use big old to try and um best average.

[01:23:48]>> Okay, let's uh see another example.

[01:23:54]Um this code is finding the maximum in an array maximum number in in this array and just imagine it can be like unsorted array that we have. So what this doing is actually checking first consider the first item as the max and then check all other items and comparing with the one that already put in the max and if every time you find a larger number which replace the previous max with the one that find. So in this scenario you think what is the best average or worse uh complexity for this algorithm.

[01:24:57]How many times you need to search to find the maximum here? Just give you some help.

[01:25:08]Uh again you don't need to counting okay you don't need to count line by line based on the example that we saw we we see that the main number of stairs comes when you have a loop. So you just need to have a look that how many loops you have if is nested or is a separate loop.

[01:25:29]And the second things you need to have a check the steps is it increasing decreasing dividing or multiplying. So you just give me that dominant case. You don't need to skip step by step. Yes.

[01:25:42]>> Is it always?

[01:25:44]>> Yes.

[01:25:47]>> Is always N because doesn't matter is the first item, middle item or the last item. You will check all the items. So it's always O N.

[01:26:03]This one is early black. Uh is want to search to find which item is zero. If there is a zero in this array, if it is zero, it will break and then stop searching. How about this one? What is the best average or worst case here?

[01:26:27]Looking for zero in array.

[01:26:31]What is one?

[01:26:35]>> The best is one because my zero will be the is the first item in the array. The average it can be somewhere in the middle. So you check n / two half of the actually array or in worst case it can be the last one or it will not even exist.

[01:26:55]So it will be O1 O N O N for M / 2 we again say O N we don't have O N / two because we always ignore the constant. Okay.

[01:27:08][clears throat] So in middle also in average also it is O N.

[01:27:16]How about this one?

[01:27:18]We have an S2.

[01:27:37]What this code is actually doing it just summing the indexes. Is there any best average or worse in every cases is square n square n because it's just summing the indexes.

[01:28:03]There is no stopping condition that we say we found it we didn't find it is go further or no. So if this code is always run square n time.

[01:28:16]So the last part big or rules as I said we always care about the worst case when we looking at algorithm we want to find in worst case which is a large input data set how behave our algorithm or overall generally uh to find the big O we always drop constants constant we don't care about constant when we want to say complexity we always keep the dominant term.

[01:28:51]Um if we have a sequential statement like sequential four we add this uh different complexity that we find if it is nested we multiply and we always we ignore lower terms.

[01:29:08]This is the example. For example, if we have something 100 n, we always drop the constant. We say it's O N.

[01:29:19]We always keep the dominant term. So here we say O² N or if we have a sequential state always we keep one of them because it will be two O N we drop always constant.

[01:29:37]If it is nested loop uh there is a multiply between them so will be a square n and always we ignore the lower terms so we ignore log n and the final is square n now let's [singing] see oh and you ask that we have any other class of complexity except for o n or log n uh the or algorithm can have different class of complexity. If it's just run for a constant number three times, four times, five times, we always say 01. Or it can be logarithmic, linear, log linear, quadratic, cubic, sublinear, exponential, factorial. So it depends on how many times our code is running.

[01:30:30]And this is diagram as we show how uh grow your complexity of your code constant with always less and then logarithmic linear until the worst case which is factorial which is more complex regarding the time complexity.

[01:30:56]Now let's have few example this final section complexity.

[01:31:02]Imagine you have this program this algorithm overall is one algorithm. Now we want to see the complexity of this algorithm. You don't need to do counting.

[01:31:14]Just have a look to the loop and step in each loop and based on the weak or rule tell me what is the complexity of this whole code.

[01:31:41]So what is the complexity for the upper part overall square n correct and the lower part >> log n and we always keep the dominant so I can say square n is the complexity of all code so it will be big o square n just I don't know if draw here or Where is not here?

[01:32:17]So it's overall is like this.

[01:32:23]So now you know all the detail you don't need to continue. But now you understand where is it come from. Correct? Any question? Is clear that where come from?

[01:32:33]Yes.

[01:32:35]Example five from Kanti.

[01:32:41]>> Yeah.

[01:32:46]>> Yes.

[01:32:48]>> Uh n to square n for all of them.

[01:32:53]>> Yes.

[01:32:58]How about this example?

[01:33:00]Can you tell me what is the complexity of this code?

[01:33:06]How many loop you have?

[01:33:09]You have two loops and both of them the steps are divided by two and it's a nested loop.

[01:33:27]So what is the complexity?

[01:33:35]log n².

[01:33:38]Yes.

[01:33:40]So because it is a nested so we have a square and both of them steps are dividing by two. So it's log n² this one easy.

[01:34:23]So log is not always for y for loop also we have a loop to the step because is multiplying by two again it is log this one because there are two separate loops.

[01:35:00]One is O N, one is log N. We always skip the dominant one. But overall the complexity of this code is O N.

[01:35:16]This one O N.

[01:35:27]So even it's plusing every time two steps still is O. The condition of log is apply if you are have a division or multiplication.

[01:35:39]This one >> again log n. If you want to be very precise then base is three but you can drop it not necessarily you put it. So still it is log n because every time is multiplying by three.

[01:36:08]This one, >> louder.

[01:36:38]square.

[01:36:40]>> Despite the second loop is actually based on the index coming from first loop, still it is a square.

[01:37:00]This one >> n because the second one is just a constant this one.

[01:37:22]So it is just O N.

[01:37:26]In big data when n is quite big that 10 actually doesn't matter. So the overall complexity is just all n.

[01:37:48]Last one here.

[01:37:56]>> [clears throat] >> No.

[01:38:05]>> No.

[01:38:10]>> No.

[01:38:12]When this loop is stop correct, this is the stopping condition.

[01:38:33]is bishing things.

[01:38:35]Yeah.

[01:38:38]So, any question? Now you know how to check the complexity of your code. So the most important part are loops and then checking the step in your loop and based on that you say overall complexity and always draft the constant and always stick with the dominant term. Okay.

[01:39:13]So last thing sometimes you have a multiple variable for example you have here nested loop one is until n one is until m since we don't know what number is n and m we should consider as a separate we cannot say they are almost same so here we cannot say o² n this is o n * m because we don't know actually what is n and what is m. So if you have multiple variable you keep it separate. Don't say square n here.

[01:39:58]question.

[01:40:01]>> Yes. What is >> that's every time like it is act like a factorial like it's looking for whatever you have to check all the previous again like for example in each check you have to do checks again from first of the algorithm like factor tutorial if you looking five you have to get one multiply 2 3 four so all the previous uh actually operation need to be repeat if you have a problem like that so in every step you have to check all the previous steps again then behave >> okay thank you >> I don't have example now here to show you how about this Yes. Big O N plus big O M. We cannot drop one of them because we don't know what is N and M. So we keep both of them.

[01:41:34]This one N log M.

[01:42:08]Last one this actually comparing two strings to check if they are equal or no. So what will be complexity for this piece of code? Comparing two strings character by character. As soon as find a difference between them it actually [clears throat] stop.

[01:42:46]Sorry again.

[01:42:56]two string and one of them's length can be n and another can be m. So when it is stop minimum so it will be o main n and m.

[01:43:19]Suppose that length of first is n and length of second is m. As soon as the comparison one of them will reach to the end of one of these strings this loop will stop. So it's minimum of length of these two string.

[01:43:41]So overall we see that counting give you exact number of number of steps and analysis which finding the complexity we actually show the growth of these steps and we don't care about this constants and we just keep the dominance part.

[01:44:04]Um yes that's all for today.

[01:44:09]Please don't forget to leave uh feedback so I can update the size based on your feedbacks.

[01:44:18]Thank you.

[01:44:25]>> I have a question.

[01:44:27]>> Yeah, >> just let me stop this uh stream.

[01:44:34]>> Sorry.

[01:44:45]Just stop.