Complexity Analysis
What is Complexity Analysis ?
There can be many ways to reach a destination, or many ways to get a work done. Similarly there are multiple ways to solve a problem or provide an algorithm to solve a problem. But how do we know which algorithm is more efficient than the other ? We need some parameters for such a comparison and here comes the base of complexity analysis.
Complexity of an algorithm is nothing but a function that will describe the efficiency of an algorithm depending upon the amount of data that the algorithm needs to process. There may be many parameters on the basis of which we may analyze our algorithms but there are two main domains on which the majority of our comparisons are made.
1. Time Complexity
As is evident from the name itself, it is a function for comparison of algorithms on the basis of time. This is usually done by calculating the number of steps that the algorithm has to execute for a given set of data and how the number of steps changes when we change the size of the data to be processed.
2. Space Complexity
This is a function that will analyze the variation of space needed to execute a particular algorithm when the amount of data to be processed through the algorithm is varied.
Asymptotic Analysis
Asymptotic analysis of algorithm involves analyzing an algorithm with the increase in input data in a limit to the point where the limit is nothing but the infinity. In other words we can look up at asymptotic analysis as an analysis when the input data is very big.
Amortized Analysis
This is a kind of analysis where we average the time required to perform an action over the total number of operations actually present. It is usually used to show that often there are certain algorithms, where may be single operation is very costly but if we average it out over the sequence of operations the apparent cost comes out to be really low as compared to that one single operation.
Different Notations used to Analyze Algorithms
ϴ Notation
For a given function g(n) we denote ϴ(g(n)) the set of functions such that,
0 ≤ c1 * g(n) ≤ f(n) ≤ c2 * g(n), for all n ≥ n0
O Notation
For a given function g(n) we denote O(g(n)) the set of functions such that,
0 ≤ f(n) ≤ c * g(n), for all n ≥ n0
Ω Notation
For a given function g(n) we denote Ω(g(n)) the set of functions such that,
0 ≤ c * g(n) ≤ f(n) , for all n ≥ n0
These are just mathematical representations of all the standard notations in use. Usually Big-O notation is the most commonly used notation for complexity analysis, so lets look at what we mean when we usually write the time or space complexity of an algorithm as O(n) or O(n²) or for that matter O(something..).
Note: The all of the three notations that is ϴ Notation, O Notation and Ω Notation can be used to depict all the three scenarios — the best case, the average case and the worst case.
O(1)
This means that no matter how much we increase the amount of data to be processed, the amount of time required to execute the algorithm remains same. Let’s look at an example,
void printOneToTen(int input_data) {
for (int i = 1; i <= 10; i++)
cout << i << endl;
cout << "The input data is " << input_data << endl;
return;
}In this example we see that no matter what the input data is the algorithm will always take a constant time to execute. Hence, this particular algorithm has a constant time complexity which can be denoted by O(1).
O(n)
Suppose there is such a function where, when you change the value of your input data the output also changes by the same amount. Such a function will be known to have a linear time complexity, which means that as we increase the input data to be processed, the time required to process the data by the algorithm also increases by the same amount as the input data is increased.
Example -
void printTillLimit(int input_data) { for (int i = 1; i <= input_data; i++)
cout << i << endl;
return;
}
As we can see from the above example that when we increase the value of input data the number of steps the algorithm has to perform also increases by the same amount. Hence this algorithm has a linear time complexity.
O(logb n)
This is a certain kind of complexity which is confused by most of the people but it is really easy to understand. Let’s begin by looking at the very definition of logarithm.
Suppose there is an expression logb n = m. What does this statement actually mean ?
It means when b is raised to the power m we get n as the answer. In other words, b^m = n.
Now lets look at it carefully, what happens when we make the result b times of itself ?
The power increases by 1!
Yes, Lets look at it with a more specific way, (considering b = 2)
2¹ = 2
2² = 4
2³ = 8
2⁴ = 16
2⁵ = 32
If you look closely if we make the result b times (b = 2, for this exampe) of itself the power changes by one.
This is exactly what is depicted by a logarithmic complexity,
O(logb n) means if we make the input data to be processed b times of itself the number of steps taken by the algorithm to compute is increased just by one. Let’s look at an example,
void printFivePowers(int input_data) {
for (int i = 1; i <= input_data; i = i * 5)
cout << i << endl;
return;
}In the above example, lets take some values of the input data,
If the input data = 5, the loop will run 1 time,
If the input data is now made b times (here b is 5) that is 25 then the loop will run just a single time more that is 2 times.
Hence the time complexity of this algorithm can be said to be O(log5 n).
O(n²)
By now I think it is much clear what can this complexity mean. It means the number of steps that the algorithms needs to perform is nearly the square of the input data to be processed. Let’s look at an example,
void printSquare(int input_data) {
for (int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++)
cout << "*" << "\t";
cout << endl;
}
return;
}In the above example the outer loop runs n times and the inner loop runs n times for each iteration of the otuer loop, that is n * n times. Hence the complexity of this algorithm is O(n²).
What about Space Complexity ?
The space complexity is measured in the exact same way as the time complexity, only in this case instead of the number of steps that the algorithm has to perform we look at how much extra space the algorithm needs to run, and how does that change with the input data to be processed.
What about the small steps ?
You might have noticed that we talk about number of steps the algorithm will execute but often neglect many steps and consider only the loops or the steps that are more in number. This is because we are essentially analyzing the change in number of steps with the change in input data to be processed. Even if we consider the steps that are constant with input data, they will yet remain constant when we change the input data and it wont make a difference in the comparison.
What about the other complexities ?
The other complexities like O(n³), O(n!), O(log(n!)) …. and so on can be similarly evaluated by evaluating the number the steps the algorithm performs and how the number of steps changes as we change the input data to be processed, if the the number of steps is the cube of the input data to be processed the complexity is O(n³), if the number of steps is taken by an algorithm is n! where n is the input data to be processed the complexity of the algorithm is O(n!) and so on.
