Algorithm
Algorithm is a step-by-step procedure to solve Logical and Mathematical problems.In simple word, Algorithm is a set of steps to solve a Problem . Here, Steps means instructions which contains fundamental operators (i.e +, -, *, / etc).
Characteristics of fundamental instructions :
1) Definiteness
Every Fundamental instructions must be define without any Ambiguity.
E.g - x = x ⊥ 1 ; // Invalid Instruction
x = x + 1; // Valid Instructions .
2) Finiteness
Every Function instruction must be terminated within a finite amount of Time .
Example :
3) Every Fundamental instructions must accept atleast 0 input and provides atmost 1 Output .
Analysis of Algorithm
Analysis of an algorithm is performed at 2 different stages . Analysis of an algorithm is done before execution and after execution .
Two phases of an algorithm are as follows:
a ) Priori Analysis :
- In Priori Analysis, analysis of an algorithm is done before execution .
- It provides estimated Values .
- It provides uniform values.
- It is independent of CPU, OS and System architecture
b) Posterior Analysis :
- In Posterior Analysis, analysis of an algorithm is done after execution .
- It provides exact values .
- It provides non - uniform Values.
- It is dependent on CPU, OS and System architecture .
Algorithm Complexity:
Complexity of an Algorithm are defined by Two Factors viz:
a) Time Factor (Time Complexity )
b) Space Factor (Space Complexity )
Before Diving into the Time and Space Complexity . We have to know that complexity of any algorithm is denoted by Big O notation .
We are always interested in knowing the worst time complexity because in worst cases, How our Algorithm are performing is matter's alot .
Therefore, Worst Time and space Complexity are shown by using Big O notation .
There are various types of Big O of any algorithm which are as follows :
 |
Complexity of an Algorithm |
In the above graph , you can see the best complexity is O(1). These shows that, as the input data size increases our algorithm will be a constant in performance . These is by far the Best Time and space complexity . In Similar fashion , We have another complexity which are as follows :
- constant complexity - O(1)
- Linear Complexity - O(n)
- Logarithm Complexity - O(log n )
- Quadratic Complexity - O(n^2)
And so on ....
Now, We can dive into the Time and Space Complexity.
a) Time Complexity :
- Time Complexity of an algorithm is the representation of the amount of time required by the algorithm to execute to completion .
- Time requirements can be denoted or defined as a numerical function t(N), Where t(N) can be measured as the number of steps provided each steps takes constant time .
Example : Finding a summation of first N natural numers
Solution - 1
Time Complexity - O(n)
Solution - 2
Time Complexity - O(1)
As you can see , Solution 2 is by far the best solution .
b) Space Complexity
Space Complexity of an algorithm represents the amount of memory space needed the algorithm in its Life cycle .
Space needed by an algorithm is equal to the sum of following 2 Components which are as follows :
1) Fixed Part
- A fixed part that is a space required to store certain data and variables, that are independent of the size of the problem.
E.g - Constant , Variables etc.
2) Variable part
- A variable part is a space required by variables, whose size depends on the size of the problem.
E.g - Dynamic memory allocation, recursive stack space etc.
Example - Summation of an element in an array .
In the above code , let's assume the size of variable x , i , result is 4 bytes and size of an arrays depends upon the number of element * size of each element .
Therefore , Space Complexity = 4n + 12
since , 4 and 12 are constant therefore we ignore that term .
Total space complexity = O(n)
