Total delay in N X M (N>=M) array multiplier due to AND gate in partial products at all level is just 1 unit AND gate delay as the operation is done parallel wise at each step. Now delays at level 1 to (M-1) is = (M-1)*delay due to 1 unit of N bit adder. Therefore the maximum gate delay is O(M) but here M=N therefore O(N).
Number of gates used in ‘n’ bit array multiplier (n * n) = (2n – 1)
Each gate in the circuit has a unit delay.
Total delay = 1 * (2n – 1 ) = O(2n – 1) = O(n)