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

Database management system, what is time out based schemes in concurrency c...

what is time out based schemes in concurrency control

Affective functioning - integrated test result, Mr. X's MMPI suggests that ...

Mr. X's MMPI suggests that he either suppresses anger and hostility or has a naturally low level of anger and hostility (O-H=58, ANG=36, TPA=41, AGGR=36). His responses on the PAS

How to add cell padding, Q. How to Add Cell Padding? As you can see, te...

Q. How to Add Cell Padding? As you can see, text is too close to the edges of the cells. You will add padding to the cells to leave room between text and cells. 1.  Click in

Write a program to echo the string, Write a program to echo the string 'Hel...

Write a program to echo the string 'Hello' to the serial channel (SCI) using the protocol of baud rate 9600,8 bits , no parity and 1 stop bit  Consider the baud register as show

What is rom, What is ROM? Read only memory [ROM] is used for storing pr...

What is ROM? Read only memory [ROM] is used for storing programs that are permanently resident in the computer and for tables of constants that do not change in value as the pr

Define interrupts and instruction cycle, Q. Define Interrupts and Instructi...

Q. Define Interrupts and Instruction Cycle? Let's precise the interrupt process, on the event of an interrupt, an interrupt request (in form of a signal) is concerned to CPU. T

Relation ship, what is relationship among objects in software engineering??...

what is relationship among objects in software engineering??

What is meant by stacked list, What is meant by stacked list? A stacke...

What is meant by stacked list? A stacked list is nothing but secondary list and is showed on a full-size screen unless you have specified its coordinates using the window comm

Explain about the term business-to-customer, Explain about the term busines...

Explain about the term business-to-customer. B2C (business-to-customer): "Electronic commerce" is usually understood mostly as selling goods or services to people ("last

Explain derived equations and models, Each student will be assigned a binar...

Each student will be assigned a binary system. The experimental references and the conditions are indicated in the table below. The student should make use of software available on

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