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
The grouped SQL statements are known as Transactions (or) A transaction is a collection of actions embused with ACID properties.

Q. Explain Types of Redundancy Checks? Parity Check Simple Parity Check Two Dimensional Parity Check / Longitudinal Redundancy Check (LRC) CRC (Cyclic Redund

Multicast An identifier for a set of interfaces (typically belonging to dissimilar nodes). A packet sent to a multicast address is delivered to all interfaces identified by tha

Twisted Pair Cable Twisted pair cable  consists of two insulated copper  wires  each  about 1 mm  thick arranged in a regular spiral  pattern. The wires  are twisted together

What are the basic LAN topologies? The three simple LAN topologies that are combined to shape any practical topology are called as basic LAN topologies. They are, Bus Topology

Sequence Number After  the bytes have been numbered TCP assigns a sequence number to each segment   that is  being sent. These sequence number for each segment  is the numb

Explain the transport layer in detail Transport Layer: Transport layer ensures and controls the end-to-end integrity of data message propagated via the network  amid two devic


Internet  Mail Access Protocol Another  mail access  protocols  is internet  mail access  protocols  version 4 (  IMAP4). IMAP4 is  similar to POP3 but it  has more  feature

Tree interconnection network:   In tree interconnection network, processors are organised in a complete binary tree pattern. Figure: Tree interconnection network