In this blog post, I am going to discuss the complexity of an algorithm. An algorithm is a procedure which indicates the body of your program for a specific task.
We will explore about How is the complexity of an algorithm calculated? What is asymptotic complexity of an algorithm? What do you mean by complexity?
In computer science, the study of the algorithm is a big and important task. There could be many algorithms to complete one task but to check the efficiency of the algorithm we can have various criteria to measure the efficiency of our algorithm.
To understand the complexity of an algorithm lets take an example, Suppose P is an algorithm and q is the size of input data. The time and space taken by the algorithm P are the main measures for the efficiency of P.
The main key operations like searching and sorting algorithm help to identify the time for executing a specific operation, such as the number of comparison in finding a specific element.
And in the same manner, space is measured by counting the maximum memory taken by an algorithm in terms of size q input data. In general, the space required by an algorithm is multiple of input data size q.
What are the types of the complexity of an algorithm?
The complexity of an algorithm is broadly classified into two types:
The space complexity can be defined as space cover-up by a program for its completion. And this space is a sum of multiple components explained given below.
A fixed part that contains a space for the code, space for a simple variable, and fixed-size component variable, space for contents, etc.
And a variable part is reserved for the variable component whose size depends on the particular problem instance being solved and the stack space used by recursive procedure.
The space requirement s(p) of any program P can be written as :
s(P) = c+sP
Where c denotes the constant and sp indicates instance characteristic
The time complexity is defined as a time to run a program for its completion.
The time T(p) taken by a program P is the summation of run time and compile time. The compile-time does not depend on the instance characteristics. So only run time of a program is going to matter, which is denoted by Tp.
Tp(n) = CaADD(n)+CsSUB(n)+CmMUL(n)+CdDIV(n)+…………
The complexity of an algorithm is concerned around the time and space were taken by that algorithm to complete a specific task. time complexity is the total time taken by the program for completion of a task and space complexity is the total space covered by the program to complete the task. So the algorithm depends on the time and space taken by it.
Using this blog we have gone through How is the complexity of an algorithm calculated? What is the asymptotic complexity of an algorithm? What do you mean by complexity? What is the need of measuring the complexity of an algorithm, Time complexity of algorithms?
In the case of any queries, you can write to us at [email protected] we will get back to you ASAP.
Hope! you would have enjoyed this post complexity of an algorithm along with its type of time complexity and space complexity.
Please feel free to give your important feedbacks in the comment section below.
Have a great time! Sayonara!