Analysis and Design of Algorithms (Shefali Singhal) (z-library.sk, 1lib.sk, z-lib.sk)

Analysis and Design of Algorithms A Beginner's Hope By SHEFALI SINGHAL NEHA GARG FIRST EDITION 2018 Copyright © BPB Publications, INDIA ISBN: 978-93-8655-189-4 All Rights Reserved. No part of this publication can be stored in a retrieval system or reproduced in any form or by any means without the prior written permission of the publishers LIMITS OF LIABILITY AND DISCLAIMER OF WARRANTY The Author and Publisher of this book have tried their best to ensure that the programmes, procedures and functions described in the book are correct. However, the author and the publishers make no warranty of any kind, expressed or implied, with regard to these programmes or the documentation contained in the book. The author and publisher shall not be liable in any event of any damages, incidental or consequential, in connection with, or arising out of the furnishing, performance or use of these programmes, procedures and functions. Product name mentioned are used for identification purposes only and may be trademarks of their respective companies. All trademarks referred to in the book are acknowledged as properties of their respective owners. Distributors: BPB PUBLICATIONS 20, Ansari Road, Darya Ganj New Delhi-110002 Ph: 23254990/23254991 BPB BOOK CENTRE 376 Old Lajpat Rai Market, Delhi-110006 Ph: 23861747 MICRO MEDIA Shop No. 5, Mahendra Chambers, 150 DN Rd. Next to Capital Cinema, V.T. (C.S.T.) Station, MUMBAI-400 001 Ph: 22078296/22078297 DECCAN AGENCIES

4-3-329, Bank Street, Hyderabad-500195 Ph: 24756967/24756400 Published by Manish Jain for BPB Publications, 20, Ansari Road, Darya Ganj, New Delhi-110002 and Printed by Repro India Pvt Ltd, Mumbai PREFACE As we are moving forward in this current computer era, we emphasize on those techniques which are more efficient and economic. This book offers a variety of algorithm's design technique, their complexity, efficiency and many more aspects. It also focuses on algorithms for games and for various machines used by us in our daily life. Keeping in mind the changing scenario in software development, Authors are confident to explain algorithmic techniques which may prove as a first step for a beginner. This book is written as per the syllabus of Diploma in Computer Science, B.Tech./B.E., BCA, Bsc., M.Tech./M.E., MCA, Msc. The book is organized in 10 chapters. Chapter 1 & 2 provides the basics of algorithms and their complexity. Chapter 3 contains divide and conquer techniques. Chapter 4 & 5 explains greedy and dynamic approach with basic comparisons between them. Graph theory is explained in chapter 6 providing a basis to use dynamic as well as greedy algorithms for various kinds of trees. Chapter 7 & 8 discuss about backtracking, branch and bound techniques which deal with problems with tree data structure. Then we talk about string matching algorithms in Chapter 9 . Lastly, chapter 10 covers NP problems. All the basic concepts have been discussed in above chapters, however, for practice session students may follow chapter wise review exercises and the set of question papers in Appendix. Although the content has been supervised by many senior educationists, there may be some shortcomings. As human is prone to errors, authors wish to forgive the mistakes and we welcome your suggestions and criticism if any! The authors will try their best to incorporate such valuable suggestions in the subsequent editions of this book. DEDICATED TO This book is dedicated to our dearest parents and beloved husband who ever and ever supported us in all respects of life and career. This journey of ours proved to be a boon by following their words and experiences. “Behind every young child who believes in himself is a Parent who Believed First” Mathew Jacobson ACKNOWLEDGEMENT First and foremost, we would like to thank God as we could never have done this without the faith we have in the Almighty. We would like to express our gratitude to the Computer Science & Engineering Department of Manav Rachna International University for always being good to us. We would extend our gratitude to the BPB Publication for bringing out the book in its present form. A great thanks to our family and friends, without their support we wouldn't be able to complete this task. “Parents are always been the boost up part behind a rising sun”. Shefali Singhal Neha Garg Table of Contents Chapter 1: Algorithm & Algorithmic Strategy 1.1 Algorithm 1.2 History

1.3 Scope of Algorithms in different fields 1.4 Classification Of Algorithms 1.5 Pseudo Code 1.6 How to design an algorithm? Review exercise Solution of review exercise Chapter 2: Complexity of Algorithms 2.1 Analysis of algorithm 2.2 Complexity 2.3 The Asymptotic Notations 2.4 Relational Properties to be applied on Asymptotic Notations 2.5 Standard notations and common functions 2.6 Basic Efficiency Classes 2.7 Logarithmic Rules 2.8 Recurrence Relation 2.9 Sorting Techniques Review exercise Multiple choice questions & answers Solution of review exercise Chapter 3: Divide-and-Conquer Algorithms 3.1 Introduction 3.2 General Divide & Conquer Recurrence 3.3 Median and Order Statistics 3.4 Binary Search 3.5 Finding Maximum and Minimum 3.6 Merge Sort 3.7 Quick Sort 3.8 Select K th Smallest Element 3.9 Strassen's Matrix Multiplication 3.10 Convex Hull 3.11 Summary Review exercise Multiple choice questions & answers Chapter 4: Greedy Algorithm

4.1 Optimization Problem 4.2 Greedy Algorithm 4.3 Coin change problem 4.4 Activity selection problem 4.5 Knapsack Problem 4.6 Job sequencing problem with deadlines (task scheduling algorithm) Review Exercise Multiple choice questions & answers Chapter 5: Dynamic Programming 5.1 Dynamic Programming 5.2 Matrix Chain Multiplication 5.3 Longest Common Subsequence 5.4 Optimal Binary Search Tree 5.5 0/1 Knapsack Problem 5.6 Travelling Salesman Problem Review exercise Multiple choice questions & answers Chapter 6: Graph Theory 6.1 Binary Tree 6.2 Binary Search Tree 6.3 Huffman Code 6.4 Graph 6.5 Minimum Spanning Tree 6.6. Single Source Shortest Path 6.7 Shortest Paths and Matrix Multiplication (All Pair Shortest Path Problem) 6.8 The Floyd-Warshall Algorithm Review exercise Multiple choice questions & answers Chapter 7: Backtracking Algorithms 7.1 Backtracking Algorithm 7.2 N Queen Problem 7.3 Sum of subsets 7.4 Graph Coloring 7.5 Hamiltonian Cycle Review Exercise

Multiple choice questions & answers Chapter 8: Branch and Bound 8.1 Branch and Bound 8.2 The Knapsack Problem 8.3 Travelling Salesman Problem Review Exercise Multiple choice questions & answers Chapter 9: String-Matching Algorithms 9.1 String Matching 9.2 Notations and Terminology 9.3 Lemma: (Overlapping and Suffix Lemma) 9.4 Classification Of String Matching Algorithm Review exercise Chapter 10: P And NP Problems 10.1 Introduction 10.2 Polynomial (P) Problems 10.3 Nondeterministic Polynomial(NP) Problems 10.4 Optimization Problems and Decision Problems 10.5 Reduction 10.6 NP Hard Problems 10.7 Cook's Theorem 10.8 Bounded Halting Review exercise Appendix C HAPTER -1 Algorithm & Algorithmic Strategy In this chapter student will understand: What is an Algorithm? From where this term is originated? Why should one study algorithm? What is the role of an algorithm in other fields? What will happen if algorithms vanish from the picture? 1.1 Algorithm Given a particular problem, how one can solve it on the computer? The way you solve any problem in systematic manner by using some input, by following proper sequence of steps and finally getting the desired output. Hence we may say that solving a problem is just like following a recipe to cook a dish. As we can see that a recipe is a box of steps and following those steps in proper sequence will always give the output. Once we design any algorithm, we need to know how well it works for a given input. Is there any algorithm better than this? In order to answer much such type of queries, algorithm analysis came into the picture.

1.2 History The term algorithm was named after the name of a Persian author, Abu Ja'far Muhammad IbnMusa'al Khowarizmi (c. 825 A. D.), who has given the definition of the algorithm as: An algorithm is a set of rules for carrying out computation either by hand or by some machine. It is a set of procedures that use some input and give desired output. He said that an algorithm must satisfy the following properties: Input: finite no of input must be externally supplied. Output: At least one output must be produced. Definiteness: Each instruction must be clear with respect to upper bound. Effectiveness: Each instruction must have a meaningful result after execution. Finiteness: If each instruction is executed in a proper sequence then the process must successfully terminate in finite time without going into any infinite loop. 1.3 Scope of Algorithms in different fields Practically every task that you perform using a computer system depends indirectly on an algorithm that someone has worked previously very hard to make sense of it. Indeed, even the simplest application on a cutting edge computer would not be conceivable to be utilized without calculations. Algorithms are being utilized to oversee memory and load information from the hard drive. Obviously, there are circumstances when you'll come across a problem that has not been previously studied. In these cases, you have to come up with a new algorithm or apply an old algorithm in a new way. More you think about algorithms in this case better is the odds of discovering rationale to take care of the issue. In many cases, a new problem can be reduced to an old problem without excessive amount of effort, but you need to have a basic fundamental understanding of the previous problem in order to solve the current one. As an example of this, let's consider what a switch does on the Internet. A switch has N cables plugged into it and gets bundles of information rolling in from the links. The switch has to first analyze the packets and then send them back to the correct cables. A switch, similar to a PC, is controlled by a clock with discrete strides - the packets are sending out at discrete intervals, rather than continuously. In a fast switch, we want to send out as many packets as possible during each interval, so they don't stack up and get dropped. The objective of the algorithm we need to create is to convey how many packets as could be expected under the circumstances during each interval, and furthermore also to send them out with the goal that the ones that arrived earlier get sent out earlier. In this case, it turns out that an algorithm for a problem that is known as “stable matching” is specifically material to our concern, though at first glance this relationship appears to be far-fetched. Only through pre-existing algorithmic knowledge and understanding such a relationship can be found. Algorithms have a vital role in different areas, few of which we have discussed below Data Structures is the real area for existing algorithms and also for generation of new algorithms. Cryptography is another study area in computer science where all the techniques like RSA, AES, DES, etc. are completely based on the algorithm. Manufacturing units fully utilize automation. There an algorithms who plays an important role. In biological field, things like a number of genes in DNA, ECG coding algorithm, etc. In the electrical field like embedded programming for IC's, magnetic resonance imaging (MRI), etc. 1.4 Classification Of Algorithms

The classification of an algorithm is based on repetitive execution of the steps and control transfer from one statement to another. By repetitive steps, an algorithm can be further classified into two types. Direct Algorithm : In this algorithm, one should know the number of iterations in advance. For example, to display numbers from 1 to 10, the loop variable should be initialized from 1 to 10. The statement would be as follows for (j=1;j<=10;j++) In the above statement, it is observed that the loop will iterate ten times. Indirect Algorithm : In this type of algorithm, repetitively steps are executed. It is totally unknown that how many repetitions are to be made. For example, the repetitive steps are as follows. To find the first five Armstrong numbers from 1 to n, where n is the fifth Armstrong number. To find the first three palindrome numbers. Algorithm on the basis of selection structure Recursive Algorithm : This type of algorithm solves the base cases directly, recurs with a simpler sub problem and does some extra work to convert the solution to the simpler sub problem that produces a solution to the given problem. Example : To count the number of elements in a list. Tower of Hanoi problem Note: A recursive method is a method that calls itself either directly or indirectly. Each repetition of the process is called iteration and the result of iteration is used as the starting point for the next iteration. Based on the control transfer, there are three categories of algorithms which are discussed below: Deterministic: A Deterministic algorithm is either follows a ‘yes’ path or ‘no’ path based on the condition. In these algorithms, when control reaches for decision logic, two paths ‘yes and ‘no’ are shown. Now the program control follows one of the routes depending upon the given condition. Example: Testing whether a number is even or odd. Testing whether a number is positive or negative. Non-Deterministic: In this type of algorithm to reach to the solution, we have one of the multiple paths. Example: To find a day of a week. To find a path between two stations like, path from Delhi to Chennai.

Random algorithm: Random algorithms are algorithms that make some spontaneous decision during their execution. After executing few instructions the control of the program transfers to another, randomly. Example: A random search Random Key generator in cryptography. 1.5 Pseudo Code In computer theory, we distinguish between algorithm and computer program. Algorithms satisfy the property of finiteness while the program may run in an infinite loop due to waiting for some resource to be allocated, couldn't find terminating condition, etc. Pseudo code is the informal and compact representation of computer programming algorithm that uses conventions of the structured programming languages like C, C++, etc. It is only intended for human reading rather than machine reading, that's why we write pseudo code in the natural language. There is one more method to represent algorithm in the symbolic representation called flowchart, but we can draw them only for simpler and smaller algorithms. Pseudo-code typically hides details that are not much essential for understanding the algorithm or may create complexity, such as functions (or subroutines), variable declaration, semicolons, special words and so on. Any version of pseudo-code is acceptable as long as its instructions are unambiguous. Pseudo-code is independent of any programming language. It cannot be compiled or executed, and do not follow any syntax rules. Pseudo Code Convention Give an appropriate name to your pseudo code and your variables. An identifier must begin with a letter. The steps are numbered. Subordinate numbers and/or indentation must use for dependent statements in selection and repetition structures. Use “//” for comments. For input use word READ . There is no need to declare variable type. For output use word DISPLAY < variable name>. For simple computation use word COMPUTE expression Example : Write Pseudo code to add two numbers Read a, b Compute c as sum of a and b Display c. For assignment use “←.” Selection Single-Selection IF IF condition THEN (IF condition is true, then pass control to subordinate statements of 1, etc. If condition is false, then skip statements) 1.1 Statement 1 1.2 Etc. Double-Selection IF and ELSE IF condition THEN (IF condition is true, then execute subordinate statement of 1, etc. If condition is false, then skip statements and execute statements under ELSE) 1.1 statements 1 1.2 etc.

ELSE (else if condition is not true, then do subordinate statement of 2, etc.) 2.1 statement 2 2.2 statement 3 END IF Example: Write Pseudo code to find whether a given number is even or odd. Read a Compute modulus of a and 2 If the modulus of a and 2 is zero Then i. Display a is even Else i. Display a is odd end if Switch case Switch (expression) TO (1) case 1: action1 (2) case 2: action2 (3) etc. (4) default: action x Repetition WHILE condition (while condition is true, then execute subordinate statements) do While(condition) do 1.1 statement 1 1.2 etc. Example: Write Pseudo code to print numbers from 1 to 10 while i<10 do i. Display i ii. i← i +1 end while. Do (DO - WHILE structure like WHILE, but tests condition at the end of the loop. Thus, the instructions in Do-block will be executed once compulsorily.) do 2.1 statement 1 2.2 etc. while condition Example: Write Pseudo code to print numbers from 10 to 1 I do

(i) Display A (ii) A ← A - 1 II while A> 0 For upper and lower bounds of repetition For (intial;condition;increment/decrement) 3.1 statements 1 3.2 etc. Array elements are represented by specifying the array name followed by the index in square brackets. For example, indicates the i th element of the array A. Example: Pseudo code for inserting ten elements in an array A[10] of size 10. For j ← 1 to 10 do 1.1 Read A[j]. 1.2 j ← j + 1. end for. 1.6 How to design an algorithm? In computer science, designing an algorithm is an art or skill. Before actual implementation of a program, designing an algorithm is a necessary step. Suppose we want to build a house we do not directly start constructing the house. Instead, we can consult an architect, we put our ideas and suggestion, the architect note it down and makes changes in the plan accordingly. This process continues till we are satisfied. Finally, the blue print of house get ready. Once the design process is over actual construction of building will start. Now it becomes very easy and systematic for the construction of desired house. In this example, you will find out that all designing is just a paper work and at that instance, if we want some changes then those can be easily carried out on paper. After a satisfactory design, the construction activities start. Same is a program development process. Let us list “ what are the steps to be followed while designing and analyzing an algorithm ”? These steps are as follows: Understanding the problem Decision making on (a) Capabilities of computational devices (b) Choosing either exact or approximate method for problem-solving (c) Data structures (d) Algorithmic strategies Specification of algorithm Algorithmic verification Analysis of algorithm Implementation or coding of algorithm

Fig.: Steps in Analysis and Design of Algorithm Let us now discuss each step in detail: 1. Understanding the problem In this step, first of all, you need to figure out the problem statement completely. While realizing the problem statement, read the problem description carefully and ask questions for clarifying the doubts about the problem. After understanding the problem statements find out what are the necessary inputs for solving that problem. The input to the problem is called the instance of the problem. It is essential to decide the range of inputs so that the boundary values of the algorithm get fixed. The algorithm should work correctly for all valid inputs. 1. Decision making After finding the required input set for the given problem we have to analyze the input and need to decide certain issues: Capabilities of computational devices Globally we can classify an algorithm from the execution point of view as: Sequential Algorithm

It mainly runs on the machine in which the instructions are executed one after the other. Such a system is called as random access machine (RAM). Parallel Algorithm These algorithms run on the machine which executes the instructions in parallel. Other than this, there are certain complex problems which require a huge amount of memory or the problems for which execution time is a major factor. For solving such problems, it is essential to have a proper choice of the computational device which is space and time efficient. Choice for either exact or approximate method for problem-solving If the problem needs to be computed correctly, then we need the exact algorithm . Otherwise, if the problem is too complex that we won't get the proper solution then in such cases we usually choose approximation algorithm . For example, traveling salesman problem follows the approximation algorithm. Data structures Data structure and algorithm work together as they are interdependent. Hence the choice of proper data structure is required before designing the actual algorithm. To implement the designed algorithm, i.e., for programming, we need the data structure. Algorithmic strategies An algorithmic strategy is a general approach by which numerous issues can be resolved. Sometimes it is called as algorithmic techniques because algorithms are categorized based on areas of computing. Here we strategize the best approach to utilize an algorithm. More than one existing method might be apply to a particular problem, many a time an algorithm developed by one approach provide better solution than one, constructed using alternative techniques. Few existing techniques areas below: Brute Force Brute force is an approach to directly solve a problem based on the given problem's statement, set of inputs, expected output and definitions of the concepts involved. Mostly they are useful for small domains, or we may say for simpler problems, due to overheads in sophisticated approaches. It is sometimes less efficient than other techniques in the general case. Some examples of brute force algorithms are: Computing an (a > 0, n a non-negative integer) by multiplying aa…*a Computing n! Selection sort Bubble sort Sequential search Exhaustive search: Traveling Salesman Problem, Knapsack problem. Greedy Algorithms Greedy Algorithms “take what you can get now” strategy A greedy algorithm repeatedly executes a procedure which tries to maximize the return based on examining local conditions, with the hope that the outcome will lead to a desired outcome for the global problem. Now and again such a strategy is ensured to offer optimal solutions in a localized manner, and in some different cases, it might provide a compromise that produces acceptable approximations. Typically, the greedy algorithms employ the strategies that are simpler to implement and require the minimal amount of resources. Examples: Minimal spanning tree

Shortest distance in graphs Greedy Algorithm for the Knapsack problem The coin exchange problem Huffman trees for optimal encoding Greedy techniques are mainly used to solve optimization problems. They do not always give the best solution. It has been proven that greedy algorithms for the minimal spanning tree, the shortest paths, and Huffman codes always provide the optimal solution. Divide-and-Conquer, Decrease-and-Conquer These are methods of designing algorithms that took an instance of the problem to be solved, split this into several smaller sub-instances (of the same problem), independently solve each of the sub-instances and after that combine the sub- instance solutions to yield a solution for the original problem. With the divide-and-conquer technique, the span of the problem instance is reduced by a factor (e.g. half the input size), while with the decrease- and-conquer method the size is reduced by a constant. Examples of divide-and-conquer algorithms: Computing an (a > 0, n a nonnegative integer) by recursion Binary search in a sorted array (recursion) Merge sort algorithm, Quick sort algorithm (recursion) The algorithm for solving the fake coin problem (recursion) Examples of decrease-and-conquer algorithms: Insertion sort Topological sorting Binary Tree traversals: in order, preorder and post order (recursion) Computing the length of the longest path in a binary tree (recursion) Computing Fibonacci numbers (recursion) Reversing a queue (recursion) Warshall's algorithm (recursion) Dynamic Programming Dynamic programming is a favor name for using the divide-and-conquer technique with a table. It is a stage-wise search method suitable for optimization problems whose solutions might be seen as the consequence of a succession of choices. The basic idea of dynamic programming is: avoid calculating the same stuff twice, for the most part by keeping up a table of known results of sub problems. The dynamic programming is a paradigm of algorithm design in which an optimization problem is solved by a combination of caching sub-problem solutions and appealing to the “principle of optimality.” Dynamic Programming is a Bottom-Up Technique in which the smallest sub- instances are explicitly solved first and the consequences of these are used to develop solutions to progressively larger sub-instances. In contrast, Divide-and-Conquer are a Top-Down Technique which logically advances from the initial problem split down to the smallest sub- instance via intermediate sub-instances. Examples:

Fibonacci numbers computed by iteration. Warshall's algorithm implemented by iterations Transform-and-Conquer Transform and Conquer is an algorithm design technique which works in two stages; STAGE 1: ( Transformation stage ): The problem's instance is modified, that is more amenable to the solution. STAGE 2: ( Conquering stage ): In this step the transformed problem is solved. The three main variations of the transform & conquer differ by the way a given instance is transformed: Instance Simplification: Transformation of an instance of a problem to an instance of the same problem with some specific property that makes the problem easier to solve. Example: list pre-sorting AVL trees Representation Change: Changing one representation of a problem's instance into another representation of the same instance. Example: 2-3 trees, Heaps and heap sort Problem Reduction: Transforming a problem given to another one, that can be solved by a known algorithm. Example: Reduction to graph problems Reduction to linear programming Backtracking For many real-world problems, the solution process comprises of working your way through a sequence of decision points in which every choice drives you further along some path. On the off chance that you make the correct set of decisions, you end up with the solution. On the other hand, if you reach a dead end or otherwise find that you have made an incorrect choice incidentally, you need to backtrack to a past decision point and attempt analternate path that may lead you to the solution. Algorithms that are implemented using this approach are called backtracking algorithms . Backtracking uses depth-first search usually without cost function. Example: Solving Puzzles such as eight queens puzzle, crosswords, verbal arithmetic, Sudoku, Peg Solitaire. Combinatorial optimization problems such as parsing and the knapsack problem. Logic programming languages such as Icon, Planner and Prolog, which use backtracking internally to generate answers. Branch-and-bound Generally, Branch and bound is used when we represent our problem in a state- space tree form in a breadth-first manner. Then evaluate each node of this tree using the cost and utility functions. By evaluating node at each step, we choose the best node to proceed further. Branch- and-bound algorithms are implemented by using a priority queue. Example: The 8 queen problem and puzzle problem. The cost function is the number of moves. The utility function evaluates how close a given state of the puzzle to the goal state is, e.g. counting how many queens are not in place.

Specifications There are various ways by which we can specify an algorithm- All the ways have discussed in the above topics. Algorithmic Verifications Algorithmic verification means checking the validity of algorithm. We can check it for a set of correct outputs by giving a valid set of input values for a finite period of time. A proof of algorithm can be complex at many a times. To show that algorithm is not working properly we have to show that for at least a given input instance it is giving an incorrect value. Analysis of algorithm To choose the best algorithm for a particular task, we need to be able to judge how long a particular solution will take to run. To analyze an algorithm is to determine the amount of resources (such as time and storage) necessary to execute it. Usually, the efficiency or complexity of an algorithm is stated as a function relating the input length to the number of steps (time complexity) or storage locations (space or memory complexity) required to execute the algorithm. Implementation of algorithm Implementation of the algorithm should be done in appropriate language. We should write an optimal code to reduce the burden of the compiler. REVIEW EXERCISE Define algorithm. Explain the role of the algorithm in various fields. State and explain the properties of an algorithm. What are the various stages needed to be followed while designing and analysis of an algorithm? What is the analysis of an algorithm? What is the complexity of an algorithm? Explain time and space complexity? Write an algorithm to find whether a given number is prime or not. Write an algorithm to calculate Fibonacci series up to the nth number. Write an algorithm to find the greatest number in an array. SOLUTION OF REVIEW EXERCISE

C HAPTER -2 Complexity of Algorithms In this chapter student will understand: What is the analysis of Algorithm? What is the role of analysis of algorithm? How one can compute the complexity of an algorithm? 2.1 Analysis of algorithm More than one algorithm might work to perform the same operation, but some algorithms use more memory and take longer time to execute than others. Also, how would we realize that calculation will work better when all is done, given differences between computers and data inputs? This is how algorithm analysis comes into play. One way to test an algorithm is to run a computer program and see how well it works. The problem with this approach is that it only tells us how well the algorithm does with a particular machine and set of inputs. The purpose of algorithm analysis is to check and then conclude how well a particular algorithm works in general. This analysis would be extremely troublesome and tedious undertaking to do on singular PCs, so specialists device models of PC is working to test algorithms. In general, algorithm analysis is about discovering how much time a program takes to run (Running time), and how much memory storage it needs

to execute the same program (Memory space). Specifically, computer science researchers do algorithm analysis to decide how the information is input into a program which affects its aggregate running time, how much memory space needed for program information, how much space the program's code requires in the memory, regardless of whether an algorithm produces correct results, how complex a program is, and how well it manages the outcomes. 2.2 Complexity The complexity of an algorithm is a function describing the efficiency of the algorithm regarding the amount of data the algorithm must process. There are measuring units for the domain and range of this function. In simple words, the complexity of an algorithm is a measure of the amount of time and memory space required by an algorithm for an input of a given size (n). By resources to be estimated, complexity is classified as below: (1) Time Complexity (2) Space Complexity 2.2.1 Time Complexity Time complexity is a function describing the amount of time an algorithm takes regarding the number of inputs to the algorithm. “Time” measure the number of memory accesses performed, the number of comparisons between integers, the number of iterations in inner loop executes, since there are many factors unrelated to the algorithm that can affect the real time (like the language used, type of computing hardware, proficiency of the programmer, optimization in the compiler, etc.). Syntax: T (A, n) where T is the number of elementary instructions executed, A is algorithm and n denotes the size of data input. 2.2.2 Space Complexity Space complexity is a function describing the amount of memory (space) an algorithm takes regarding the number of inputs given to the algorithm. We often speak of “extra” memory required, never take into account the memory needed to store the input itself. Here, we use natural (but fixed- length) units to measure the space. We can use bytes, yet it is easier to utilize, the number of integers used, the number of fixed-sized structures, and so forth. At last, the function we think will be independent of the actual number of bytes expected to represent the unit. Space complexity is sometimes ignored because the space used is minimal but sometimes it becomes as important as time. Syntax: S (n) where S is the space required by the set of functions computable in space, at most c*S (n) for some constant c>0, where n is input size. 2.2.3 Worst-case, Best-case, Average case complexities Worst-case complexityz: complexity (number of times the basic operation executed) for the worst case is found for input of size n, hence the algorithm runs for longest time as compared to all possible inputs of size n. If complexity is indicated by function f (n) then in worst case, it is indicated by the maximum value of f (n) for any possible input. Best-case complexity: complexity (number of times the basic operation executed) for the best case is calculated for input of size n., when the algorithm runs the fastest as compared with all possible inputs of size n. Here, the value of f(n) is minimum for any possible input. Average-case complexity: Average time was taken (number of times the basic operation executed) to solve all the possible instances (random) of the input. The value of f (n) lies in between maximum and minimum for any possible input. Note: Here the average doesn't mean by the average of worst and best case. 2.3 The Asymptotic Notations We are usually interested in the order of growth of the running time of an algorithm, not in the exact running time. These notations are also used to represent the asymptotic running time. We have to build up an approach to discuss the rate of growth of functions so that we can compare algorithms. Asymptotic notation gives us a method for classifying the functions according to their rate of growth.

The Asymptotic notation is a shorthand way to write down and talk about ‘the fastest possible’ and ‘the slowest possible’ running times for an algorithm, utilizing highest and lowest bounds on speed. It mainly measures computation time of any algorithm. The primary Asymptotic Notations are: θ (Theta) Notation [Average number of steps to solve a problem, (used to express both upper and lower bound of a given f (n)] Ο (Big-“Oh”) Notation [Maximum number of steps to find a solution to the problem, (upper bound)] Ω (Big-“Omega”) Notation [Minimum number of steps to execute the problem, (lower bound)] 2.3.1 Theta Notation (θ-Notation) Here f (n) and g (n) are two functions, n is the set of positive integers, and n 0 is an input till which the above-given condition may or may not follow. But after it, the relation is always valid. As shown in the graph below: θ- Notation is “asymptotically tight bound” because of its equivalence from both upper and lower bound. 2.3.2 Big-Oh Notation (O-Notation) (Read it as “f of n is big oh of g of n” or “f is big oh of g”) Here f (n) and g (n) are two functions, n is the set of positive integers, and n 0 is an input value till which the above given condition may or may not follow. But after it, the relation is always valid, as shown in the graph below. O-notation is a “tight upper bound notation”, and it provides maximum value of running time for any given function. 2.3.3 Omega-Notation (O-Notation) Here f (n) and g (n) are two functions, here n is the set of positive integers, and n 0 is an input till which the above-given condition may or may not follow. But after it, the relation is always valid, as shown in the graph below.