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
Continuous or Discrete - artificial intelligence: The behaviour of the coming data in from the environment will change how the agent should be programming. In particular, the

What is a thread? A thread otherwise called a lightweight process (LWP) is a basic unit of CPU utilization, it comprises of a thread id, a program counter, a register set and a

What is an AVL tree? AVL Tree An AVL tree is a binary tree in which the dissimilarity in heights among the left and the right subtree is not more than one for each node.


What are the main characteristics of a pipeline? Ans: The main characteristics of a pipeline are: a) The speedup or efficiency gain by suing a pipeline depends on the numbe

Write the importance of operating system. Describe the working methodology of online and real-time operating system with the help of two examples of each.

design modulo 12 up synchronous counter using t flip flop


Question: (a) What are the rationales for an effective and independent regulator? (b) Across Africa, regulators have established Universal Service Funds (USFs) in order to

The excess 3 code of decimal number 26 is ? Ans. (26) 10 in BCD is (00100110) BCD Add 011 to all BCD 01011001 for excess - 3