Introduction

• Algorithm → An algorithm is a sequence of unambiguous instructions for solving a problem in a finite amount of time.

Important features of Algorithms

1. Algorithms must always be non-ambiguous.
2. The range of inputs for which an algorithm works has to be specified carefully.
3. An algorithm can be implemented in multiple ways.
4. There can exist several algorithms for solving the same problem.

Characteristics of Algorithms

1. Input → Zero or more quantities externally supplied
2. Finiteness → Algorithm terminates in a finite number of steps.
3. Effectiveness → Each instruction must be primitive and feasible.
4. Output → Atleast one output is produced.

Algorithm Design Techniques

• A general approach to solve problems algorithmically.
• Examples of Algorithm Design Techniques:
  • Brute Force
  • Divide and Conquer
  • Transfer and Conquer
  • Greedy
  • Dynamic Programing
  • Branch and Bound
• The choice of the data structure used to implement the algorithm can dramatically change its time complexity.

Complexity of Algorithms

• Complexity is the performance of an algorithm.
• An algorithm’s performance is characterized by the following:
  • Time complexity → How fast an algorithm maps input to output, as a function of the input.
  • Space complexity → Amount of memory units required by the algorithm in addition to the memory needed for its input and output.
• Complexity of an algorithm can be determined by:
  1. Experimental Study (Performance Measurement)
  2. Theoretical Analysis (Performance Analysis)