Introduction to Time Complexity

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:-

  1. Linear Search
  2. 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 :-

  1. Binary Search :- O(log2(n))
  2. Linear Search :- O(n)
  3. Quick Sort :- O(n*log2(n))
  4. Selection Sort :- O(n*n)
  5. Merge Sort :- O(n*log2(n))