The complexity of an algorithm shows how fast or slow that particular algorithm can solve the desired problem.
- We can also define it as, it is a measurement of the amount of time and/or space required by an algorithm for a given input of size (n) to solve a problem.
- Basically, we denote complexity with the help of numerical function T(n).
- Where T(n) is a function of time versus input size n.
- A given algorithm may take different amounts of time on the same amount of inputs because time depends on various factors such as the speed of the processor, instruction set, disk speed, brand of compiler and etc.
We caculate the complexity of any algorithm in these three senarios
1). Worst Case
It denotes the maximum run time that could be taken by an algorithm over all inputs of size n. That is, we only consider the “number of times the principle activity of that algorithm is performed.”
2). Best Case
In the best case, we look at specific instances of input of size n and assume a happy case. For example, suppose we want to sort a list, but our input list is already sorted then here algo performs its best behavior.
3). Average Case
It is the most useful measure for the complexity of an algorithm. Generally, the worst case and best case behavior are extremely rare, So that we are more concerned about how the algorithm runs in the general case.
Type of complexity
- Time complexity
- Space complexity
1. Time complexity
The time complexity of an algorithm gives the total amount of time taken by the program to complete its execution.
- Big O asymptotic notation is commonly expressed the time complexity of algorithms.
- Time Complexity is estimated by counting the number of principle activity or elementary step performed by an algorithm to finish execution.
Let’s take an example to understand time complexity:
For any problem, there may be N number of solutions are available, but our main aim is to choose only those solutions which are efficient for our problem. Our solution should give the result in less time.
We can write many programs for a single problem. Let’s See the below example to understand this concept. Below are the two different algorithms to find a square of a number:
for i=1 to n do n = n + n // when the loop ends n will hold its square return n
Above both solutions is to find the square of the given number. In the first solution, we have calculated the square using “for” loop. Here “for” loop is running for n times, every time it starts with the number n and adding n to it.
Because of the loop is running n times, so time complexity will be n at least in this case. When the value of n increases the time taken by the program to complete the execution will also increase.
In the second solution mathematical operator “*” has been used to calculate the square of a number. It will take only constant time, so it’s time complexity will be constant.
So in this two solutions second one is best.
The performance of an algorithm may vary with different types of input data. So, for the time complexity analysis we analyze in the worst case because worst-case analysis gives the maximum amount of time taken by an algorithm to complete execution for input size n.
2. Space Complexity :
Space complexity analysis for an algorithm is an analysis to calculate the total amount of memory taken by an algorithm to complete execution and give the desired result for an input n. In space complexity analysis input value to the algorithm is also considered.
To execute an algorithm, it should gets loaded on the main memory. The memory is taken by an algorithm is in different forms:
1). Variables (This includes the constant values and temporary values)
2). Program Instruction
Auxiliary space is extra space or temporary space used by the algorithms during its execution.
Various memories is usages by program during its execution
Instruction Space: It is used by the program to save compiled instruction in the memory.
Environmental Stack: It is used to store the addresses while a module calls another module or functions during execution.
Data space: It is used to store data, variables, and constants which are stored by the program and it is updated during execution.