This is the single Guide that you need before starting DSA 😍

Algorithm are independent of programming language. This is something which is not related to programming language. You don't have to relate the DSA with the programming because DSA is a separate topic. Means a step-by-step procedure, or you can also say that a set of instructions which are predefined for solving any particular task or any particular problem. Ladies and gentlemen, so hello everyone, welcome back to my YouTube channel. In today's video, we are going to dive into the very interesting topic that is related to the algorithm, and we are going to learn each and everything in detail. I am damn sure that by the end of this video you are going to totally understand what is exactly Big O notation, why is it important in your coding journey, and how you have to implement it in your coding journey. So let's get started. Okay, so let's first understand what is algorithm. Algorithm means a step-by-step procedure, or you can also say that a set of instructions which are predefined for solving any particular task or any particular problem. Algorithm are independent of programming language. This is something which is not related to programming language. You don't have to relate the DSA with the programming because DSA is a separate topic. So in DSA algorithms comes, but in programming language algorithms are nothing. So meaning that they can be implemented in any programming language, okay? So if you are learning DSA, then it is not related to any programming language. If you have the knowledge of Python, it doesn't mean that you can only solve DSA with the Python. You can implement algorithm with any programming. So now let's talk about what is a good algorithm. We know what is algorithm— step-by-step procedure. What are the characteristics? Basically, first thing is it should produce the correct output for all the possible valid inputs. Second, it should minimize the uses of computational resources like time and space. Third is the algorithm must always terminate after a finite number of steps. Fourth is each step of algorithm should be clearly defined. If any algorithm has 4 characteristics, then it means this is a good algorithm. Now let me give you some examples of the algorithm. Algorithms are like sorting algorithm, search algorithm, graph transfer algorithm. Search algorithms like binary search or linear search. Sorting algorithms like merge sort or quick sort, right? Now let's talk about Big O notation. Big O notation is something which tells how efficient your algorithm is. So let's take an example. Let's say you are participating in a race. When you participate in the race, it will be good if you know that how much time you are going to take. Let's say the race is of 3 hours, but you yourself know that what is your strength and how much you can run and how much time you are going to take. It means how fast you are going to run, and second thing is how much time you are going to take. So fast and time, these two things you know. If you know, then you can easily win the race, right? Same thing is applicable in Big O notation. Big O notation is typically a way for algorithm to predict that how much time your algorithm is going to take if it will run on this particular input set. Also, if the input grows, then also how much time will it take or how much storage. So there are multiple algorithms. Now your task is to choose one which is best for your project, best for your application or the websites that you are creating. So there are two types of complexity. First is time complexity, second is space complexity. Both are the part of the Big O notation because the time complexity and space complexity is expressed in the format of Big O. Big O means O is a notation which you have to use every time to define time. Just like we have kilometers, meters, centimeters, same way we have Big O, which is O is for the notation. So it goes like O, O, O, O. All these are the notations which are used to define time complexity and space complexity. So now let's dive into the concept of time complexity. The time complexity means it is going to refer to the amount of time an algorithm is going to take to execute a function of the size of the input. Now it is basically going to estimate the running time of the algorithm in the worst case, good case, average case, every case. Okay, now depending on how it analyzed, you have to finalize your algorithm for your project. Now let's first understand what is the purpose. Basically, we wanted to know time complexity, that how much time it is going to take. But why is— first thing is we are going to predict the performance of the algorithm. If we can predict, suppose my website is going to take the load of 100 users, my website can easily load at the same time on 100 devices. But what if there are 1000 users? What if there are 1000 visitors on my website? How will it work, or whether it will work or not? So these type of questions comes up. So if I can predict the performance of my website or my algorithm, then I easily scale it up. So understand how an algorithm will scale when the input size is going to increase. Second thing is you are going to compare the algorithm. As I am saying from the beginning, that you have to evaluate different algorithm based on the different execution time for large input, helping you choose the efficient one for your problem. Now let's talk about some time complexity. First is O. O means this is the constant time. Constant time means the execution time depends doesn't depend upon the input size. So however the input size is going to be, whether it is the larger number or smaller number, anything, then if the time cons— time is constant, then it will take same time. If it was taking a task to complete 1 hour, then it will take 1 hour for the same. Well, I can say that if I wanted to access any element from the array, we all know that array is an indexed one. Array has the numeric, like number 1, 0, 1, 2, 3, 4. Indexing starts from 0. So if I wanted to access 5th element, then I can simply use these square brackets and I can mention that I want 5th element. If I want 10th one, I have to just mention 10. In both the cases, in the 5th element and 10th element, array is going to take the same time. So this is the constant time example, that it means both of the cases, no matter what is the value that you are going to search for. With the real world example, if you wanted to know, then it means suppose you are looking for a book, but that book is already in your bookmarks, so it will be pretty easy for you to look for that book which you are looking for. Second is O. O means linear time. It means the execution times grow— time grows linearly when the input size increases. It means if the input size is increasing, the time of the execution will also increase, which is basically directly proportional to the input size. If input size is increasing by 5, then obviously your time will also increase by 5. For an example, let's say you are checking for a book in a shelf. So that shelf consists of, let's say, 50 books. So out of that 50 book, you have to go line by line and you have to check. And let's say there are— in a library, there are 5 shelves. So you have to go to 5 shelves and you have to search for each one of them. That is where the linear time comes in. Third is the O. It is the quadratic time. It is execution time grows with the square of the input size. So for an example, let's say there are 2 shelves in which you have to search for the books. But let's say your books are arranged in some categories like rom-com books, novels, educational books, and you are looking for the educational books. Let's say you're looking for the educational book. Now what your task is, you have to create a pair. When it comes to create a pair, then creating a pair from both the shelves one book from this shelf, another book from this shelf, so that we can keep it on the top, like related to education. So when you are comparing and finding a perfect match, that is where the quadratic time comes in. Then comes the log n. Log n is generally seen all over the DSA. So logarithmic time means time will grow logarithm— instead of checking each element, your algorithm is going to neglect the larger amount. Now let's take an example of your contact book. In your contact book, the numbers which are— you have saved are arranged in the alphabetical order, A to Z or Z to A. You can switch. So finding a number in those kind of books or those kind of directories, it is easy. That is where logarithmic time is applicable. And the last one is exponential time, which is O. Execution time doubles with the each input, with the each additional input. Okay, try every possible combination to unlock 10-digit lock, let's say. So what will happen? 10-digit lock, it means there will be n number of possibilities to get that. Perfect example is Fibonacci The Fibonacci series is the example of the quadratic time because in Fibonacci series the recursive algorithm that you are going to type is— so I hope this makes it pretty easy for you to understand that what exactly these Big O notations is and how this Big O notation works. So why time complexity is important? Because of the scalability of the application, because of the efficiency of the application, because of the— because of handling large datasets. These are the 3 big examples why we have to deal with the time complexity and why we have to exactly calculate. Then comes space complexity. Space complexity is going to measure the memory it is going to take. Suppose earlier when you tested the algorithm, it was with the 10 input, 10 input size, but now you are dealing with the 1000 input size. So when it comes to the 1000 input size, now you have to do what? You have to check also the space, that whether it is going to take more space or what. If you can measure the amount of the memory that algorithm uses to process the input, then it will be easier to choose the best cloud package and also to go with the things according. Now, what is input size? Input size means in terms of array, I can say that number of elements in the array, number of characters in a string, number of vertex or edges in the graph. These are the input size. There are multiple data types, so multiple input size will be there. According to the data type, your input size is going to be different. So same thing is applicable in the space complexity as well, but we are going to have a separate video on that, that what exactly space complexity is. So to remember everything, let's have a look. O means instant access, like opening a bookmark page. Second is O, which is line-by-line search, like scanning a ship. Third is the O , which is a smart shortcut, like a phone book search. Fourth one is the O, which is comparing all pairs, like pairing items in a group project. Fifth one is the exponential time. It is like exploding option, like trying every password combination. So this is a quick way to remember all the Big O notation so that it makes your coding and DSA journey easy. Let me know in the comments if you want any other video on this topic. Or so, if you have understood it well, don't forget to subscribe to the channel and check out the documentation in the description which I have added completely for everything. And let me know in comments what other topics you want me to cover in the upcoming videos and feedback of this video. Bye!