Analysis of sort_bitonic, Computer Networking

The bitonic sorting network needed log n number of stages for performing the task of sorting the list. The first n-1 stages of the circuit are able to sort two n/2 numbers and the last stage uses a +BM (n) comparator having the depth of log n. As running time of the sorting is dependent upon the entire depth of the circuit, thus it can be depicted as:

D (n) = D (n/2) + log n

Answering the above mentioned recurrence relation

D (n)= (log2 n + log n)/2  = O(log2 n)

Thus, the complexity of solving a sorting algorithm using a combinational circuit is

O (log2 n).

 

Posted Date: 3/2/2013 6:43:28 AM | Location : United States







Related Discussions:- Analysis of sort_bitonic, Assignment Help, Ask Question on Analysis of sort_bitonic, Get Answer, Expert's Help, Analysis of sort_bitonic Discussions

Write discussion on Analysis of sort_bitonic
Your posts are moderated
Related Questions
What is a protocol? The term protocol refers to a set of rules and process that govern the transmission of messages over a physical networking medium. The most common network p

simple introduction,defination and with example & digram

NETWORK INTERFACE HARDWARE:  CPU can't operate data at network speeds. So in order to connect to the network device systems use special purpose hardware for network connection

Besides these hardware overheads, there are certain software overheads imposed by libraries, parallel compilers, tools and operating systems. The parallel programming languages

In distributed data processing, explain two scenarios where vertical partitioning and horizontal partitioning are used. Distributed Data Processing The distributed data pro

Encoding data options PVM uses SUN's XDR library to generate a machine independent data format if you request it. Settings for the encoding option are: PvmDataDefault: Use X

Token Bus Frame Format No length field Data is able to be much larger (timers prevent hogs) Frame control Ack required? Data vs Control frame and how is


Consider an RTP session consisting of five users, all of which are sending and receiving RTP packets into the same multicast address. Each user sends video at 200kbps. a)  What

Q. What do you understand by OSI? Ans: The Open System Interconnection (OSI) reference model illustrates how information from a software application in one computer goes throug