Search code examples
complexity-theorydigital-logic

Time complexity in n bit array multiplication


Consider an array multiplier for multiplying two n bit numbers. If each gate in the circuit has a unit delay, the total delay of the multiplier is ?

  1. Θ(1)
  2. Θ(logn)
  3. Θ(n)
  4. Θ(n^2)

Solution

  • Multiplication of unsigned numbers using array of full adders

    If you see the image above you will notice that delay caused is diagonal to the array.
    So the delay is approxiamtely sqrt(2)*(2n-1).
    Which is Θ(n)