Analysis of sort bitonic, Computer Engineering

Analysis of Sort_Bitonic(X)

The bitonic sorting network needs log n number of phases for performing task of sorting the numbers. The first n-1 phases of circuit can sort two n/2 numbers and the last phase uses a +BM (n) comparator having the depth of log n. As running time of sorting relies upon the total depth of the circuit so it can be stated as: 

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

  Solving above written recurrence relation

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

  So the complexity of solving a sorting algorithm employing a combinational circuit is O (log2n).

 One more famous sorting algorithm called merge sort based algorithm can also be solved with help of combinational circuit.

Posted Date: 7/10/2013 7:47:24 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
Explain bit pair recoding with an example? Ans: Bit pair recoding halves the maximum number of summands. Group the Booth-recoded multiplier bits in pairs and see the following

Define Instruction Code. An Instruction code is a group of bits that instructs the computer to perform an exact operation. It is usually separated into parts, each having its o

Define Modem. A modem changes digital signals into audio tones to be transmitted over telephone lines and also changes audio tones from the lines in digitals signals for machin

Q. FORALL Statement in fortran? The FORALL statement permits for more common assignments to sections of an array. A FORALL statement has general form.   FORALL ( triplet, ..

what is fresnel''s biprism?how it is used to determine wavelength of monochromatic source of light

The decimal equivalent of (1100) 2   is ? Ans. (1100) 2 = (12) 10

Specify the goals of parsing. Goals: a. To check the validity of source string b. To agree on the syntactic structure of a source string. For invalid string this rep

Q. What is the impact of overflow for binary numbers? An overflow is said to have happened when sum of two n digits number takes n+ 1 digits. This definition is perfectly appli

Define BCD. A binary code that distinguishes between 10 elements must contain at least 4 bits, but 6 combinations will remain unassigned. Numerous dissimilar codes can be obtai

QWERTY-based keyboards In addition the standard alphabet keys having QWERTY arrangement, a computer keyboard also comprises the control (alt, Del, Ctrl etc. keys) and function