Algorithms and Complexities PDF

**ALGORITHMS AND COMPLEXITIES** **Algorithm** ------------- The word algorithm has been derived from the Persian author\'s name, Abu Ja \'far Mohammed ibn Musa al Khowarizmi (c. 825 A.D.), who has written a textbook on Mathematics. The word is taken based on providing a special significance in com...

**ALGORITHMS AND COMPLEXITIES** **Algorithm** ------------- The word algorithm has been derived from the Persian author\'s name, Abu Ja \'far Mohammed ibn Musa al Khowarizmi (c. 825 A.D.), who has written a textbook on Mathematics. The word is taken based on providing a special significance in computer science. The algorithm is understood as a method that can be utilized by the computer as when required to provide solutions to a particular problem. An algorithm can be defined as a finite set of steps, which has to be followed while carrying out a particular problem. It is nothing but a process of executing actions step by step. An algorithm is a distinct computational procedure that takes input as a set of values and results in the output as a set of values by solving the problem. More precisely, an algorithm is correct, if, for each input instance, it gets the correct output and gets terminated. An algorithm unravels the computational problems to output the desired result. An algorithm can be described by incorporating a natural language such as English, Computer language, or a hardware language. **Characteristics of Algorithms** --------------------------------- - **Input:** It should externally supply zero or more quantities. - **Output:** It results in at least one quantity. - **Definiteness:** Each instruction should be clear and ambiguous. - **Finiteness:** An algorithm should terminate after executing a finite number of steps. - **Effectiveness:** Every instruction should be fundamental to be carried out, in principle, by a person using only pen and paper. - **Feasible:** It must be feasible enough to produce each instruction. - **Flexibility:** It must be flexible enough to carry out desired changes with no efforts. - **Efficient:** The term efficiency is measured in terms of time and space required by an algorithm to implement. Thus, an algorithm must ensure that it takes little time and less memory space meeting the acceptable limit of development time. - **Independent:** An algorithm must be language independent, which means that it should mainly focus on the input and the procedure required to derive the output instead of depending upon the language. **Advantages of an Algorithm** ------------------------------ - **Effective Communication:** Since it is written in a natural language like English, it becomes easy to understand the step-by-step delineation of a solution to any particular problem. - **Easy Debugging:** A well-designed algorithm facilitates easy debugging to detect the logical errors that occurred inside the program. - **Easy and Efficient Coding:** An algorithm is nothing but a blueprint of a program that helps develop a program. - **Independent of Programming Language:** Since it is a language-independent, it can be easily coded by incorporating any high-level language. **Disadvantages of an Algorithm** --------------------------------- - Developing algorithms for complex problems would be time-consuming and difficult to understand. - It is a challenging task to understand complex logic through algorithms. Need of Algorithm ================= 1\. To understand the basic idea of the problem. 2\. To find an approach to solve the problem. 3\. To improve the efficiency of existing techniques. 4\. To understand the basic principles of designing the algorithms. 5\. To compare the performance of the algorithm with respect to other techniques. 6\. It is the best method of description without describing the implementation detail. 7\. The Algorithm gives a clear description of requirements and goal of the problem to the designer. 8\. A good design can produce a good solution. 9\. To understand the flow of the problem. 10\. To measure the behavior (or performance) of the methods in all cases (best cases, worst cases, average cases) 11\. With the help of an algorithm, we can also identify the resources (memory, input-output) cycles required by the algorithm. 12\. With the help of algorithm, we convert art into a science. 13\. To understand the principle of designing. 14\. We can measure and analyze the complexity (time and space) of the problems concerning input size without implementing and running it; it will reduce the cost of design. **The criteria of an algorithm** -------------------------------- - - - - - **Analysis of algorithms** -------------------------- **Complexities of an Algorithm** -------------------------------- **Time Complexity of an Algorithm** ----------------------------------- **Space Complexity of an Algorithm** ------------------------------------ Difference between Deterministic and Non-deterministic Algorithms ================================================================= **What is Deterministic Algorithm?** ------------------------------------ **What is Non-Deterministic Algorithm?** ---------------------------------------- -- -- -- -- -- -- 1. 2. 3. 4. 5. 6. Usually, the time complexity is determined by the size of the algorithm\'s input to the number of steps taken to execute it. Also, the space complexity is mostly determined by the amount of storage needed by the algorithm to execute. If an algorithm runs in a reasonable amount of time or space on any machine, where that time and space are measured as a function of the size of the input (usually), then the **algorithm** is considered to be **efficient**. In simple terms, if the resource consumption or the computation cost of an algorithm grows slowly with the growth of the size of the input, then the algorithm might be considered as **efficient**. Do not worry if these terms confuse you, we will be learning about these in great depth ahead in the article. What is the Need for Analysis of the Algorithm? ----------------------------------------------- Let\'s say you created a website where users may read and post blogs. In the early stages of development, the website\'s user base is quite small (say 10−2010−20 users). But with time, the number of users on your website grows dramatically, reaching **40k** -- **50k** users. Now, the questions that will start popping into your mind are: 1. Will my website scale well with these many users? 2. Or, it would start lagging and take a great time to respond to any user? So, these issues would not arise if you had addressed them when designing your website. But, if you neglected these factors in the beginning, then there are higher chances that your code will crash for indefinitely large inputs. Hence, here the analysis of algorithms comes into the picture! Let us now see why is the analysis of the algorithm so important: - By analyzing an algorithm, we get an idea of **how the algorithm will scale** with the variation (change) in the input size. - Another reason for analysis of the algorithm is to compare various algorithms for solving the same problem. Through this, we can determine which algorithm will suit best the problem. Suppose, we have 2 algorithms for a single problem, one that takes *O*(*N*2) and another that takes *O*(*N*). Then we can say that the algorithm with a **time** complexity of *O*(*N*) will perform much better than the one with *O*(*N*2). - Analysis of the algorithms also helps us in understanding the **space** that will be taken by our code. Analyzing algorithms is an essential aspect of computer science and programming. It involves evalua ting the efficiency and performance of an algorithm in terms of its time complexity, space complexity, and other relevant factors. Here are some reasons why analyzing algorithms is important: 1. Efficiency: By analyzing an algorithm, you can determine how efficiently it solves a problem. Efficiency is crucial because it directly impacts the execution time and resource usage. An algorithm that is more efficient will generally provide faster results and consume fewer computational resources. 2. Comparison: Analyzing algorithms allows you to compare different approaches to solving the same problem. By understanding their time and space complexities, you can identify the most suitable algorithm for a given scenario. This helps in making informed decisions and optimizing program performance. 3. Scalability: The performance of an algorithm can vary depending on the input size. Analyzing algorithms helps in understanding how their efficiency scales with larger inputs. This is particularly important when dealing with large datasets or computational problems that require processing significant amounts of data. 4. Optimization: Analyzing algorithms can reveal potential bottlenecks and areas for improvement. By identifying inefficient parts of an algorithm, you can optimize or redesign those sections to enhance overall performance. This optimization can save computational resources, reduce execution time, and improve user experience. 5. Resource Allocation: In many real-world applications, resources such as memory, processing power, or network bandwidth are limited. Analyzing algorithms helps in determining how much of these resources an algorithm requires to solve a problem. This information is valuable for efficient resource allocation and system design. 6. Prediction: Algorithm analysis provides insights into how an algorithm is expected to perform in different scenarios. It helps in predicting the behavior of an algorithm and estimating its performance under various conditions. This knowledge is crucial for designing robust systems and managing user expectations. 7. Algorithmic Research: Analyzing algorithms is fundamental to algorithmic research and the development of new algorithms. By understanding the strengths and weaknesses of existing algorithms, researchers can devise novel approaches to tackle complex problems more efficiently. Overall, analyzing algorithms is essential for developing efficient and optimized software systems. It enables programmers and researchers to make informed decisions, improve performance, and provide better user experiences. What are Asymptotic Notations? ------------------------------ Asymptotic notations in general tell us about how good an algorithm performs when compared to another algorithm. However, we cannot simply compare two algorithms directly. To compare two algorithms, factors such as the hardware and the tools we are using also have a remarkable impact. For example, the performance of algorithms varies with variations in the operating systems, the processors, etc. So, even though we\'ve calculated the performance of two algorithms on a particular system, there are chances that they will perform differently on different systems. To tackle the above-stated issues, we use the asymptotic analysis to compare the space and time complexity of the algorithms. The asymptotic analysis analyzes two algorithms based on their performance when the input size is varied (increased or decreased). **There are three types of Asymptotic notations. They are as stated below:**  1. Big-O(*O*) notation. 2. Big Omega (Ω) notation. 3. Big Theta (Θ) notation. The above notations are used to measure the worst, best, and average time complexities of the algorithms. In the next point, we will understand them in detail. Types of Algorithm Analysis --------------------------- Till now we must already be aware that, the running time of an algorithm increases with the increase in the size of the input. However, if the running time is constant then it will remain constant, no matter what the input is. Algorithms are often quite different from one another, though the objective of these algorithms are the same. For example, we know that a set of numbers can be sorted using different algorithms. Number of comparisons performed by one algorithm may vary with others for the same input. Hence, time complexity of those algorithms may differ. At the same time, we need to calculate the memory space required by each algorithm. Analysis of algorithm is the process of analyzing the problem-solving capability of the algorithm in terms of the time and size required (the size of memory for storage while implementation). However, the main concern of analysis of algorithms is the required time or performance. Even if the size of the input is the same sometimes, the running time of the algorithm still may vary. Hence, we perform the best, average, and worst-case analyses of the algorithms, covering all the possible cases where the algorithm may behave abruptly high or low. Generally, we perform the following types of analysis. There are four types of analysis of algorithms. They are stated below: 1. Best case 2. Average case 3. Worst case 4. Amortized analysis Let us look at each of them in detail. ### 1. Best Case Analysis of Algorithms The best case analysis of algorithms gives us the **lower bound** on the **running time** of the algorithm for any given input. In simple words, it states that **any program will need at least** (greater than or equal to) that time to run. **For example**, suppose we have an algorithm that has the best case time complexity is *O*(*N*), then we can say that the program will take a minimum of *O*(*N*) time to run, it can never take sometime less than that. The best case time or space complexity is often represented in terms of the **Big Omega (Ω)** notation. **Example for Best Case Analysis:** Let us take the example of the linear search to calculate the best time complexity. Suppose, you have an array of numbers and you have to search for a number. **Find the code below for the above problem:** Now suppose, the number you are searching for is present at the very beginning index of the array. In that case, your algorithm will take *O*(1) time to find the number in the best case. So, the best case complexity for this algorithm becomes *O*(1), and you will get your output in a constant time. **How frequently do we use the best case analysis of any algorithm?** The best case is rarely necessary for measuring the runtime of the algorithms in practice. An algorithm is never created using the best-case scenario. ### 2. Worst Case Analysis of Algorithms The worst-case analysis of algorithms gives us the **upper bound** on the **running time** of the algorithm for any given input. In simple words, it states that **any program will need maximum that time** (less than or equal to) to run. **For example**, suppose we have an algorithm that has the worst-case time complexity is *O*(*N*2), then we can say that the program will take a maximum of *O*(*N*2) time to run, for an input of size *N* it can never take more time than that to run. The worst-case time or space complexity is often represented in terms of the **Big Oh(*O*)** notation. **Example for worst case analysis :** Let us take our previous example where we were performing the **linear search**. Suppose, this time the element we are trying to find is at the end of the array. So, we will have to traverse the whole array before finding the element. Hence, we can say that the worst case for this algorithm is *O*(*N*) itself. Because we have to go through at most *N* elements before finding our target. So, this is how we calculate the worst case of the algorithms. **How frequently do we use the worst-case analysis of any algorithm?** In actual life, we typically analyze an algorithm\'s worst-case scenario for most of the cases. The longest running time *W*(*n*) of an algorithm for any input of size n is referred to as worst-case time complexity. ### 3. Average Case Analysis of Algorithms As the name suggests, the average case analysis of algorithms takes the sum of the running time on every possible input, and after that, it takes the average. So, in this case, the execution time of the algorithm acts as both the lower and upper bound. In simple terms, we can get an idea of the average running time of the algorithm through it. Generally, the average case of the algorithms is as high as the worst-case running of it. Hence, it roughly gives us an estimation of the worst case itself. The average case time or space complexity is often represented in terms of the **Big theta (Θ)(Θ)** notation. **Example for average case analysis:** In our previous example, suppose we need to find any element which is present in the mid of our array. So, for that, we need to traverse at least the half length of the array. In other words, it will take us *O*(*n*/2) time for us to traverse the half-length. The time complexity *O*(*n*/2) is as good as *O*(*n*). That is why we say that the average case in most of the cases depicts the worst case of an algorithm. **How frequently do we use the average case analysis of any algorithm?** To be precise, it is usually **difficult** to analyze the average case running time of an algorithm. It is **simpler** to calculate the **worst case** instead. This is mainly because it might not be a very exact thing to declare any input as the **\"average\"** input for any problem. Therefore, prior knowledge of the distribution of the input cases is necessary for a useful examination of the average behavior of an algorithm, which is necessarily an impossible condition. ### 4. Amortized Analysis of Algorithms The amortized analysis of the algorithms mainly deals with the overall cost of the operations. It does not mention the complexity of any one particular operation in the sequence. The total cost of the operations is the major focus of amortized analysis. In times when only a few operations are slow but a majority of other operations are quicker, we perform an amortized analysis. Through this, we return the **average running time per operation** in the **worst case.** **Example for Amortized case analysis** A perfect example of understanding the amortized case analysis would be a **hash table**. You must have used or implemented the hash tables or dictionaries, in whichever language you code. So, in a hash table, for searching, the time taken is generally *O*(1), or constant time. However, there are situations when it takes *O*(*N*) times because it has to execute that many operations to search for a value. Similarly, when we try to insert some value in a hash table, for a majority of the cases it takes a time of  *O*(1), but still, there are cases when suppose multiple collisions occur, when it takes a time of *O*(*N*), for the collisions resolution. Other data structures we need amortized analysis are Disjoint Sets etc. **How frequently do we use the amortized case analysis of any algorithm?** Whenever a single operation or very few operations runs slowly on occasion, but most of the operations run quickly and frequently, then the amortized case analysis is used. To solve a problem, we need to consider time as well as space complexity as the program may run on a system where memory is limited but adequate space is available or may be vice-versa. In this context, if we compare **bubble sort** and **merge sort**. Bubble sort does not require additional memory, but merge sort requires additional space. Though time complexity of bubble sort is higher compared to merge sort, we may need to apply bubble sort if the program needs to run in an environment, where memory is very limited.