Introduction to Time Complexity
Introduction to Time Complexity
In the field of Computer Science, the analysis of algorithm plays an important role in solving any problem. It is very important to find the most efficient algorithm for solving any problem.
There are so many different types of algorithm to solve a problem, but we have to find the most efficient algorithm.
Now, the main problem is how we will decide that which algorithm is most efficient
for a particular types of a problem, as we have different sets of algorithm for a particular problem. Then at this stage the concept of "space and time complexity" comes into existence.
According to this concept we compare the algorithms on the
basis of their space(amount of memory) and time complexity(number of operations). In this article
we will only focus on the Time Complexity.
Time Complexity :- Time Complexity is the number of operations an algorithm performs to
complete the assigned task(assuming that each operations will take the
same amount of time). The algorithm that completes the assigned task
in the smallest number of operations is considered the most efficient one
in terms of the time complexity.
Now to understand the time complexity, we will take an example in which we'll compare two types
of different algorithms which are used to solve a particular problem.
Lets take the example of searching, we will search an element in a list(assume that the list is sorted
in ascending order). For this we will use two types of algorithm:-
- Linear Search
- Binary Search
Let's take a list which contains 10 element, and we will discuss the 3 types of cases:- best-case,
average-case and worst-case.
Suppose we have a list [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] and we have to find an element in this list using
linear search.
- Best-Case :- This is the complexity of solving the problem for the best input. In our example, the best case would be to search for the value 1. Since this is the first value of the list, it would be found in the first iteration.
- Average-Case :- This is the average complexity of solving the problem. This complexity is defined with respect to the distribution of the values in the input data. Maybe this is not the best example but, based on our sample, we could say that the average-case would be when we are searching for some value in the middle of the list, for example, the value 5 or 6.
- Worst-Case :- This is the complexity of solving the problem for the worst input of size n. In our example, the worst-case would be to search for the value 10, which is the last element from the list.
Usually, deciding the time complexity of an algorithm, we will considering the worst-case. But the question here occur is that how to decide the time complexity for any algorithm. The answer is, we
use the mathematical notation called "Big-O" notation.
Big-O Notation :- Big-O notation, sometimes called asymptotic notation, is a mathematical
notation that describes the limiting behavior of a function when the argument
tends towards a particular value or infinity.
In computer science, Big-O notation is used to classify algorithms according to how their running time or space requirements grow as
the input size (n) grows. This notation characterizes functions according to
their growth rates: different functions with the same growth rate may be represented using the same O notation.
Calculation of time complexities using Linear Search and Binary Search :-
In Linear search algorithm, it will compare each element of the list to the search_element, and
when it will find the search_element in the list then it will return true.
Now, counts the number of operations it performs. Here,
in linear search the answer is 10(since it compares with every element in the list and the element present in the list is 10). Therefore in general, Linear search will take n number of operations in
its worst case(where n is the size of list).
Now, examine for the Binary search algorithm for the same case. In Binary search algorithm, it
will first compare search_element with the middle element of the list, i.e. 5. Now since 5 is less
than 10, then we will start looking for the search_element in the list element greater then 5, in
the same way until we get the desired element 10.
Now, count the number of operations Binary search performs to find the desired element. It took approximately 4 operations. Now, this was the worst case for binary search. This shows that there is a logarithmic relation between the number of operations performed and the
total size of the list.
No. of operations = log2(10) = 4(approx)
Therefore, now we can generalize these results for the both algorithm that the time taken to
complete the task for Linear search in worst case is O(n), and the time taken to complete the
task for Binary search in worst case is O(log2(n)).
Comparision of the time complexity between Linear search and Binary search with the help of
graph is given below :-
The Time complexity or Big O notations for some popular algorithms are listed below :-
- Binary Search :- O(log2(n))
- Linear Search :- O(n)
- Quick Sort :- O(n*log2(n))
- Selection Sort :- O(n*n)
- Merge Sort :- O(n*log2(n))
*-------------*--------------*
Comments