Data Structure- Algorithm Introduction

 What is an algorithm? 

 An algorithm is a finite set of step by step instructions to solve a problem. In normal language, algorithm is defined as a sequence of statements which are used to perform a task. 

In computer science, an algorithm can be defined as follows: 

 An algorithm is a sequence of unambiguous instructions used for solving a problem, which can be implemented (as a program) on a computer. 

 Properties Every algorithm must satisfy the following properties: 

 1. Definiteness - Every step in an algorithm must be clear and unambiguous 

2. Finiteness – Every algorithm must produce result within a finite number of steps. 

3. Effectiveness - Every instruction must be executed in a finite amount of time. 

4. Input & Output - Every algorithm must take zero or more number of inputs and must produce at least one output as result. 

1.2 Performance Analysis In computer science there are multiple algorithms to solve a problem. 

When we have more than one algorithm to solve a problem, we need to select the best one. Performance analysis helps us to select the best algorithm from multiple algorithms to solve a problem. When there are multiple alternative algorithms to solve a problem, we analyses them and pick the one which is best suitable for our requirements. Generally, the performance of an algorithm depends on the following elements... 

 1. Whether that algorithm is providing the exact solution for the problem? 

2. Whether it is easy to understand? 

3. Whether it is easy to implement? 

4. How much space (memory) it requires to solve the problem? 

5. How much time it takes to solve the problem? Etc., 

When we want to analyze an algorithm, we consider only the space and time required by that particular algorithm and we ignore all remaining elements. 

 Performance analysis of an algorithm is performed by using the following measures: 

 1. Space Complexity 

2. Time Complexity 

1.2.1 What is Space complexity? 

 Total amount of computer memory required by an algorithm to complete its execution is called as space complexity of that algorithm. Generally, when a program is under execution it uses the computer memory for THREE reasons. They are as follows... 

 1. Instruction Space: It is the amount of memory used to store compiled version of instructions. 

2. Environmental Stack: It is the amount of memory used to store information of partially executed functions at the time of function call. 

3. Data Space: It is the amount of memory used to store all the variables and constants

1.2.2 What is Time complexity? 

 The time complexity of an algorithm is the total amount of time required by an algorithm to complete its execution. 

Generally, running time of an algorithm depends upon the following: 

 1. Whether it is running on Single processor machine or Multi processor machine. 

2. Whether it is a 32 bit machine or 64 bit machine 

3. Read and Write speed of the machine. 

4. The time it takes to perform Arithmetic operations, logical operations, return value and assignment operations etc.