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

Can matchcode object contain ids with different update types, Can matchcode...

Can matchcode object contain Ids with different update types? Yes.

What is the meaning of proper programming, What is the meaning of Proper pr...

What is the meaning of Proper programming Proper programming of the ports of the company's Web server through detection of IP addresses could be an excellent strategy or solut

Name the concepts of object oriented, Name the concepts of Object oriented ...

Name the concepts of Object oriented There are various concepts of object oriented analysis Abstraction, Encapsulation, Identity, Modularity, Hierarchy, Typin

Representation scheme in artificial intelligence, Representation scheme in ...

Representation scheme in artificial intelligence: It is not hard to see why logic has been popular representation scheme in AI: In this way, It is easy to represent knowl

Python implementation of a solver for the desert cro, Python implementation...

Python implementation of a solver for the desert crossing, Python Programming #Minimum 100 words accepted#

Find traffic offered and lost, Discuss grade of service. During busy hour, ...

Discuss grade of service. During busy hour, 1500 calls were offered to a group of trunks and 8 calls were lost. The average call duration was 120 seconds. Calculate the traffic off

Explain compiler, What is compiler? A system software program known as ...

What is compiler? A system software program known as a compiler translates the high-level language program into a suitable machine language program having instruction such as t

What are the advantages offered by data mining, What are the advantages off...

What are the advantages offered by data mining? Advantages offered through Data Mining are given below: a) Facilitates discovery of knowledge through massive, large data set

Algorithm of non-repudiation designing e-cash based system, Give a suitable...

Give a suitable algorithm of non-repudiation in designing e-cash based system. The algorithm of non-repudiation in designing e-cash based system is as illustrated below: Ke

What all 1's represents in 32bit ip addressing scheme, In 32bit IP Addressi...

In 32bit IP Addressing scheme all 1's represent? All 1's represent limited broadcast in 32 bit IP Addressing scheme.

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