I think the solution provided is n log2 (max(a_i)) not linear


Itarating over all the elements and for everyone their bits is not linear. Am I wrong ?


No I actually thought the same before but since the maximum integer size is 32 bits, and we are going through the 32 bits every time no matter what the elements are, it only adds a constant factor to the O (n) running time.