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

Continuous or discrete - artificial intelligence, Continuous or Discrete - ... 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, What is a thread? A thread otherwise called a lightwe... 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, What is an AVL tree? AVL Tree An AVL tree is... 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.

Area under curve,

Characteristics of a pipeline, What are the main characteristics of a pipel... 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

Describe the working of operating system, Write the importance of operating... 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.

#title.sequential circuit, design modulo 12 up synchronous counter using t ... design modulo 12 up synchronous counter using t flip flop

Computer security., what is access control what is access control

Rationales for an effective and independent regulator, Question: (a) W... 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

Find out the excess code of decimal number, The excess 3 code of decimal nu... 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