The maximum gate delay for any output to appear in an array multiplier for multiplying two $n$ bit numbers is
In an $N \times M$ array multiplier we have $N \times M$ AND gates and $(M-1),$ $N-bit$ adders are used.
Total delay in $N \times M (N\geq 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) = (M-1) \times $ delay due to $1$ unit of $N-bit$ adder. Therefore the maximum gate delay is $O(M)$ but here $M=N \therefore O(N).$
Refer this article page 16.
this may help, in last 10 mins of the video, time complexity is explained!
link change http://eee.guc.edu.eg/Courses/Electronics/ELCT706%20Microelectronics%20Lab/winter%202014/Multipliers.pdf
page no. 8
see this https://gateoverflow.in/902/gate2003-11
18th jan was the last date