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) = (log² n + log n)/2 = O (log² n)

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

 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

Ask an Expert

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

Write your message here..

Related Questions

Bit pair recoding and 2’s complement, Explain bit pair recoding with an exa... 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, Define Instruction Code. An Instruction code i... 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, Define Modem. A modem changes digital signals into audio ... 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

Forall statement in fortran, Q. FORALL Statement in fortran? The FORALL... 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, ..

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

Determine the decimal equivalent of binary 1100 ?, The decimal equivalent o... The decimal equivalent of (1100) 2   is ? Ans. (1100) 2 = (12) 10

Specify the goals of parsing, Specify the goals of parsing. Goals: ... 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

What is the impact of overflow for binary numbers, Q. What is the impact of... 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, Define BCD. A binary code that distinguishes between 10 ele... 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, QWERTY-based keyboards In addition the standard... 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