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

Explain what is high debugging?, It is helped to recure the bugs. A program...

It is helped to recure the bugs. A program has problem that time this debugging is helped to solve the bugs is simply, this is the method of the recure bugs in the programming lang

What is control function, Q. What is control function? If transfer is t...

Q. What is control function? If transfer is to take place only under a predetermined control condition then this condition can be specified as a control function. For illustrat

Categorize the cpu scheduling algorithms, Categorize the CPU scheduling alg...

Categorize the CPU scheduling algorithms? The various CPU scheduling algorithms are categorized as given below:

linq file extension, What is the LINQ file extension that interacts with C...

What is the LINQ file extension that interacts with Code Behinds objects? Ans) The extension of the file is .dbml

Define usb, Define USB. The Universal Serial Bus(USB) is an industry st...

Define USB. The Universal Serial Bus(USB) is an industry standard developed to give two speed of operation known as low-speed and full-speed. They provide simple, low cost and

Draw logic circuit for the simplified function, Minimize the logic function...

Minimize the logic function Y(A, B, C, D) = ∑m(0,1,2,3,5,7,8,9,11,14). Use  Karnaugh map. Draw logic circuit for the simplified function. Ans: In following figure (a) shows the

Illustrate about sharing of structure and behaviour, Illustrate about Shari...

Illustrate about Sharing of Structure and Behaviour  One of the reasons for the popularity of object-oriented techniques is that they promote sharing at different levels. Inher

Role of internet, What are the roles of Internet, Intranet and extranet in ...

What are the roles of Internet, Intranet and extranet in e-business? Role of Internet, Intranet and extranet into e-business: The given information activities are carried

Dram, DRAM consists of MOSFET's but the technique is to use the drain sourc...

DRAM consists of MOSFET's but the technique is to use the drain source capacitance to hold charge. If charge is present logic '1' is held, no charge logic '0'. As you know capacito

Pipe and filter , How to draw the pipe and filter using data flow and it co...

How to draw the pipe and filter using data flow and it components and connectors

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