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 difference between Baseband and Broadband Transmission in ccna? Ans) In a baseband transmission, the entire bandwidth of the cable is consumed by a one signal. In bro

INFANT MORTALITY PERIOD Initially there are a large number of failures, called initial failures or infant mortality. These failures are primarily due to manufacturing defects,

100Base-TX Uses two category 5 UTP cable pairs or else two STP cable pairs to connect stations to a hub (star) One pair holds frames from station to hub one pair from

Question 1 Write about                       Circuit Switched Networks                       Packet Switched Networks Question 2 Write about                       Protocol Indep

what is difference between Star and Mesh topology?

What are the Advantages of adaptive routing  (1) An adaptive routing method can improve performance, as realised by the network user. (2) An adaptive routing method can aid

Discuss about LAN topologies LAN topologies:   Network topology is a physical schematic that demonstrates interconnection of the many users. There are four fundamental topolog

Explain Radio Wave. Although Radio waves are common and well understood, we are just starting to realize their enormous potential as a networking medium. Radio waves can operat

Q. Explain Dynamic Domain Name System? DDNS - Dynamic Domain Name System automatically updates the DNS master file - Sent by DHCP to a primary DNS server; secondary se

You have been asked to design a Banking Network with two primary types of locations.  Branches that will have 3 subnets, one /25 subnet one /26 subnet for ABMS and one /26 s