Analysis of merge sort, Computer Engineering

Assignment Help:

i) The width of the sorting + merging circuit is equivalent to maximum number of devices needed in a phase is O(n/2). As in the above diagram maximum number of devices for a given phase is 4 that is 8/2 or n/2. 

ii) The circuit comprises two sorting circuits for sorting sequences of length n/2 and afterwards one merging circuit for merging of two sorted sub sequences (see phase 4th  in above figure). Let functions Tm and Ts signify the time complexity of merging and sorting in terms of its depth.

The Ts can be calculated as follows:  

               Ts (n) =Ts (n/2) + Tm (n/2) 

               Ts (n) =Ts (n/2) + log (n/2), 

 Therefore, Ts (n) is equal to O (log2 n).

2264_Analysis of Merge Sort.png

Figure: Sorting + Merging Circuit


Related Discussions:- Analysis of merge sort

Datatype functions for message passing, Q. Datatype Functions for Message P...

Q. Datatype Functions for Message Passing? Datatype: It denotes type of data in message. This field is essential in the sense that MPI supports heterogeneous computing and diff

Differences between asp and asp .net, What are the differences between ASP ...

What are the differences between ASP and ASP .Net ?    1. ASP: Code is Interpreted ASP.NET: Code is Compiled 2. ASP: Business Logic and Presentation Logic are in a one

Define about pascaline - mechanical computers, Pascaline:Mechanical compute...

Pascaline:Mechanical computers Blaise Pascal made the initial attempt in the direction of this automatic computing. He invented a apparatus, which comprised of lots of gears an

Data types done between abap/4 & external level, How is conversion of data ...

How is conversion of data types done between ABAP/4 & external level? Conversion among the external layer and the ABAP/4 layer is completed in the SAP dialog manager DYNP.

the entire pcd division, Will executing  SAP R/3 across the entire PCD div...

Will executing  SAP R/3 across the entire PCD division give the division with a competitive benefit?  Clarify  your answer carefully.

Explain bus interface unit, Q. Explain Bus Interface Unit? BIU (Bus Int...

Q. Explain Bus Interface Unit? BIU (Bus Interface Unit) mainly interacts with system bus. It executes nearly all the activities relating to fetch cycle like:  Computing

List out the features of computer memory, List Out the Features of Computer...

List Out the Features of Computer Memory? Features of each type of memory   Type Volatile? Write able? Erase Size

cellfun function, There is a built-in function function known as cellfun t...

There is a built-in function function known as cellfun that evaluates a function for each element of a cell array.  Make a cell array, then call the cellfun function, passing the h

What are the steps in executing the program, What are the steps in executin...

What are the steps in executing the program? 1.Fetch 2.Decode 3.Execute 4.Store

Define external variable declaration, Summarize the distinction between an ...

Summarize the distinction between an external variable definition and an external variable declaration. When we have ''declared'' a variable, we have meant that we have told th

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd