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

Two methods of copying a information document, There are basically two meth...

There are basically two methods of copying: Photocopying This is a modified development of photography. It is quite expensive and slow and is not often used for routine rep

Describe the vertical frequency or cycle, Q. Describe the Vertical Frequenc...

Q. Describe the Vertical Frequency or cycle? Like a Fluorescent lamp, the screen has to repeat same image many times per second to display an image to user. The frequency of th

Application of connect-4 game, The game Connect-4 is played on a board that...

The game Connect-4 is played on a board that has seven columns. There are six spaces on each column. The board is initially empty. Two players take turns dropping one piece (black

What is remote login, Remote Login  A login that permits a user termina...

Remote Login  A login that permits a user terminal to connect to a host computer by a network or direct telecommunications link, and to interact with that host computer as if t

Software engineering, specialization,ggeneralization and aggregation of rai...

specialization,ggeneralization and aggregation of railway reservation system?

Sdr, advantages of sdr

advantages of sdr

What is a convertor?, Converter is an application that converts distance me...

Converter is an application that converts distance measurements among metric and U.S units.

Nix commands, reate a directory "Unix" under your home directory. Command(...

reate a directory "Unix" under your home directory. Command(s): ………………………………………….

Baic electrical, Ask question #Minimumstate and explain thevenins theorem a...

Ask question #Minimumstate and explain thevenins theorem as applicable to electrical circuits 100 words accepted#

What is control unit, What is Control Unit Control Unit: The control u...

What is Control Unit Control Unit: The control unit issue control signals to perform exact operation and it directs the entire computer system to carry out keeps program instr

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