Algorithm

Hi friends, In my previous post we have came to know what is Data Structure. If not, please go to this link.

Today we are going to know about Algorithm.

Algorithm Basis

Algorithm is step by step procedure, which defines a set of instruction to be executed in an order to get the required outputs.

Following are the important categories:

1. Search
2. Sort
3. Insert
4. Update
5. Delete

Characteristics of an Algorithm:

1. Should be clear in every step.
2. Well defined Inputs.
3. Well defined and required outputs.
4. Should be finite and it should be terminated after some steps
5. Independent of any language

Algorithm Analysis:

There are 2 different stages to find the efficiency of an algorithm.
They are

1. Before Implementation
2. After Implementation

Algorithm Complexity:

The complexity of the algorithm depends on 2 factors.

1. Time factor (Time taken to complete the number of operations)
2. Space factor (Maximum memory space taken for the elements in the algorithm)

Space Complexity:

Space Complexity depends on 2 factors.

1. Fixed part (C) -> Space required to store data for certain variables, constants, program size, etc.
2. Variable Part (S(I)) -> It depends on dynamic allocation of variables/ objects, stack space etc.

S(P) = C + SP(I)

Time Complexity:

Time required to complete the program. Usually time required to complete the program goes into 3 types of categories.

1. Best Case
2. Average Case
3. Worst Case

Asymptotic Notations

There are 3 main asymptotic notations to calculate the running time complexity of the algorithm.

1. O Notation (Represents the upper bound of the algorithm which represents worst case time)
2. Ω Notation (Represents the lower bound of the algorithm which represents best case time)
3. θ Notation (Represents the both upper and lower bound of the algorithm which represents best and worst case time respectively).