Merge Sort - Time Complexity

 Time Complexity of Merge Sort


Algorithm:

 

                MergeSort(left, right){

 

                       If(left < right){

                                   Mid=(left+right)/2

 

                                   MergeSort(left,mid)

                                   MergeSort(mid+1, right)

                                   Merge(left,mid,right)

            }

 

        }






The algorithm shows, MergeSort function devices the entire array into two parts in one iteration. The Programme will terminate when it comes to One element in the array. The following diagram shows how it performs.






The total Number of Executions can be calculated by adding steps that occurred at each level. Therefore the Total number of Executions is equal to n log(n).
So the time complexity is,


                                 F(n) = O (n log(n))

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

Redux - Saga

Image
Redux is a state management tool that works as a “centralized store,” which means that it is the only place to access the state.Redux is a light “standalone” JavaScript library, which means it can be used with any UI framework, most frequently, it is used with ReactJS. Redux-Thunk Redux Thunk is a middleware that enables you to call action creators that return functions (thunks) that accept the store's dispatch method as an argument and are then used to dispatch the synchronous action after the API or side effects have ended. Redux-Saga Another middleware library that assists us with API calls or side effects is Redux Saga. Redux Saga makes use of ES6's "Generators" feature, which makes it easier to develop asynchronous code. Redux-saga’s action creator returns an Object while Redux-Thunk action creator returns a Function(thunk). Redux-Saga Data Flow How data flow When a user interacts with the application, an action is dispatched Root Reducer/ Reducer  function is c...
Read more