Quick Sort - Time Complexity

 Time Complexity of Quick Sort


Algorithm:

 

                    QuickSort(left, right){

 

                           If(left < right){

                                       Pi= partition(left,right)

 

                                      QuickSort(left,pi)

                                      QuickSort(pi+1, right)

            

                }

 

            }



The algorithm has Recursion. But the Time complexity depends on the "Partition()" function of the Algorithm.


Assuming partition is done with the middle of the array.........





Total number of Executions = n log (n)



Time Complexity = F(n) = O (n log (n ) )              ------------- (Best Case)



Note that this time complexity calculation is for the Best Case. That means partitioning is done by the middle of the array. But this is not practical. Because every array will not partition from the middle. That means achieving the best case is not possible.





So we have to consider the Worst Case



The worst-case means partitioning is done from the end of the array. partitioning will start from the starting or ending point and it will perform until it gets one element in the array. The following diagram shows an Example.






Total Number of Executions= 1+2+....+ n = n (n+1)
                                                                                 2


  Worst case Time Complexity = F(n) = O (n2)






F(n) = O (n2)  ---- (Worst Case)











Location: Balangoda, Sri Lanka

Comments

Post a Comment

Popular posts from this blog

Insertion Sort - Time Complexity

Image
 Time Complexity of Insertion Sort Selection Sort is using two for loops to do one iteration. The first loop (Outer loop ) travels through an array starting from index 0, while the inner loop runs from index i+1 to index less than i. The following diagram shows the Number of execution rounds it performs. when i is 0,, j is 1,  the inner for loop runs n-1 time. when i is 1, j is 2, the inner for loop runs n-2 times. Likewise, when i is n, j is n+1,  the inner for loop runs n times. So the total number of Execution rounds can be calculated by adding all Execution times in each i values.  Time Complexity =    n-1 (n-1)                                              2            ...
Read more

Selection Sort - Time Complextity

Image
  Time Complexity of Selection Sort  Selection sort  is using two for loops to do one iteration. The first loop (Outer loop ) travels through an array starting from index 1, while the inner loop runs from index 1 to index i-1. The following diagram shows the Number of execution rounds it performs. when i is 1, the inner for loop runs only one time. when i is 2, inner for loop runs 2 times. Likewise when i is   n   the inner for loop runs n times. So the total number of Execution rounds can be calculated by adding all Execution times in each i values.     Time Complexity       =    n (n+1)                                         2                     ...
Read more