What Is Algorithm In Ds?

Prashant | Mon, 24 Aug, 2020 | 124

Let us understand this with some basic examples of life. Think we need to buy chocolate from a shop:

  1. The first step will be taking money.
  2. Go to the shop. 
    • If the shopkeeper has chocolate
      • If yes we can buy it.
      • if no, we can terminate the plan.
  3. Come back home and eat.

What we are doing is, for a given problem (buying a bar of chocolate), we are providing a step-by-step procedure for solving it. The formal definition of an algorithm can be stated as:

An algorithm is the step-by-step unambiguous instructions to solve a given problem

In the traditional study of algorithms, there are two main criteria for judging the merits of algorithms: correctness (does the algorithm give solution to the problem in a finite number of steps?) and efficiency (how much resources (in terms of memory and time) does it take to execute the).

Note: We do not have to prove each step of the algorithm

Why Analysis of Algorithm is required

To go from city “A” to city “B”, there can be many ways of accomplishing this: by flight, by bus, by train and also by bicycle. Depending on the availability and convenience, we choose the one that suits us. Similarly, in computer science, multiple algorithms are available for solving the same problem (for example, a sorting problem has many algorithms, like insertion sort, selection sort, quick sort, and many more). Algorithm analysis helps us to determine which algorithm is most efficient in terms of time and space consumed.

The goal of the analysis of Algorithm

The goal of the analysis of algorithms is to compare algorithms (or solutions) mainly in terms of running time but also in terms of other factors (e.g., memory, developer effort, etc.)

Run time analysis

It is the process of determining how processing time increases as the size of the problem (input size) increases. The input size is the number of elements in the input, and depending on the problem type, the input may be of different types. The following are the common types of inputs.

  • Size of an array
  • polynomial degree
  • Number of elements in the matrix
  • Number of bits in binary representation
  • Vertices and edges in graphs

 

 

 

0 comments
Leave a comment