The zero-padding overhead created when performing Random Linear Network Coding (RLNC) on unequal-sized packets can curb its promising benefits since it can be as high as the data to convey. The concept of macro-symbol coding was introduced recently in order to reduce the zero-padding overhead that RLNC has brought. Macro-symbols are subsets of the packets, i.e. concatenated bytes. They allow performing coding mainly on the payload and they proved to be efficient against the naive padding. This paper studies the properties of macro-symbols and provides a characterization of their impact on the computational complexity as well as the overall overhead. Furthermore, we provide a theoretical framework for the encoding and decoding complexity for the state-of-the-art schemes for unequal-sized packets. Our simulations results performed on a series of benchmark video traces show that small macrosymbols guarantee a dramatic reduction of padding overhead, whilst it results on a higher decoding complexity on the other hand compared with RLNC in the worst case.