Time complexity is an important criteria when determining the quality of an algorithm. An algorithm is better if it produces the same result in a less time for the same input test cases.
However, one must take care of the type of input data used. Some input data can give you false positives. Let us take an example to understand this better. You have an algorithm that is sorts a list of numbers. If the input data you provide to this algorithm is already sorted. Then this algorithm gives you perfect results, in the least amount of time. However, it may be possible that any other algorithm that is statistically faster would take more time to process the input.
How can I calculate the time taken by every algorithm?
This might be a question that can bother a newbie. You cannot simply determine how much time every algorithm would take and even generating valid input data for each of the methods would be a cumbersome task.
This is the reason we call it time complexity, and not time taken.
An algorithm is an independent entity, and hence we shouldn’t be measuring its performance with the machine it is running on. Given that, we need to relate the performance of an algorithm with the input size. This is usually denoted by n. To put it in really simple terms, n determines the number of elements in the input data. Then we count the number of primitive operations carried out by the algorithm on each item.
What are primitive operations?
Primitive operations simply mean a single step instruction performed on an item. They could be like:
- Arithmetic operations like addition and subtraction
- Comparison of values using
if - Assignment of variables
- Reading from a variable.
IMPORTANT: A function call although looks like a single step, it may or may not be a primitive operation. We need to dig into the method to actually determine if it was a primitive operation.
Here are some examples:
public void run() {
int a = 1; // primitive
int b = 4; // primitive
if (b < 10) { // primitive
doSomething(a); // not primitive
}
}
public void doSomething(int a) {
// some operations on 'a'
}Code language: Java (java)To calculate the time complexity of an algorithm, we find out the number of primitive operations we are doing on each of the item in the input set. For instance, we are doing 4 operations on each item of array of size n, then the time complexity of the algorithm would be said to be 4n units.
What about conditional blocks? Based upon the input that we get, some conditional blocks will or will not execute. If executed, they add to the time complexity of the algorithm and it may take more time to run. To overcome this problem we usually observe 3 kinds of time complexities
Case analysis of Time Complexity:
- Best-case analysis: In this case, we take a specific input, to make the fewest number of primitive operations possible. An example of a best case scenario could be a sample input set of numbers which is already sorted. When we sort this set, no shuffling of the array would be required, and hence we would be having less primitive operations. This makes is a best case. But, this analysis is not useful to us, as it doesn’t tell anything about the time taken for an actual use case.
- Average-case analysis: In this analysis, we try to determine the average number of primitive operations called for a variety of test inputs. This is not easy as it sounds. To calculate an average-time we must also know the frequency of sample input sets as well. Suppose we write an algorithm to sort a set of numbers, we need to know the average size of elements. Along with it, we also need to know how many input sets, would be small, and how many would be large. The average case analysis is usually not beneficial as it can change on a case by case basis.
- Worst-case analysis: This is the most essential analysis we can hope to achieve when calculating the time complexity. We chosen such that the algorithm will encounter maximum number of primitive operations possible. This metric is really helpful as it helps in determining the maximum amount of time an algorithm can take to execute. Based on this time, we can then write our further logic while developing large scale applications.
Video Explanation:
