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

State about the directed-test methodology, Directed-Test Methodology Bu...

Directed-Test Methodology Building a directed verification environment with a comprehensive set of directed tests is very time-consuming and difficult. As directed tests only c

What are the types of operations required for instructions, What are the va...

What are the various types of operations required for instructions?  Data transfers among the main memory and the CPU registers Arithmetic and logic operation on data

what is feram?, Ferroelectric RAM is a random-access memory same in constr...

Ferroelectric RAM is a random-access memory same in construction to DRAM but uses a ferroelectric layer rather of a dielectric layer to achieve non-volatility. FeRAM is one of a gr

Explain handlers classification, Handlers Classification In 1977, Wolfg...

Handlers Classification In 1977, Wolfgang Handler suggested a complex notation for representing the pipelining and parallelism of computers. Handler's categorization addresses

Displaying the towers of hanoi solution, Once you have a solution to the To...

Once you have a solution to the Towers of Hanoi problem, we want to improve the display of the solution. The details of the implementation are up to you. At a minimum, your impleme

Describe the graphic accelerators, Q. Describe the Graphic Accelerators? ...

Q. Describe the Graphic Accelerators? A Graphic Accelerator is actually a chip as a matter of fact most significant chip in your video card. The Graphic Accelerator is essentia

Information security, i wants to know the methods and process of substituti...

i wants to know the methods and process of substitution and transposition cipher with examples.

Describe language processing activities, Describe language processing activ...

Describe language processing activities? There are two different kinds of language processing activities: a. Program generation activities b. Program execution activities

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