# J, <s>110</s> <s>104</s> 95 bytes, O(n log n)

    f=:((#~((+,-)(%_1^i.@#%#))&f(#~-.))1:`0:\)^:(1<#)
    9 o.<:@+&#{.[:(f%#)[:+@*/,:f@{."1~2^2>.@^.+&#

Uses the Convolution theorem which states that the Fourier transform of the convolution of two sequences is equal to the Fourier transform of each sequence multiplied together elementwise.

    Fourier( Convolve(a, b) ) = Fourier(a) * Fourier(b)
    Convolve(a, b) = InverseFourier( Fourier(a) * Fourier(b) )

Also uses the fact the the inverse Fourier transform can be applied by using the Fourier transform of the conjugate.

    InverseFourier(a) = Conjugate( Fourier( Conjugate(a) ) ) / Length(a)

I used the FFT implementation from a previous [solution][1]. That implementation uses the Cooley-Tukey [algorithm][2] for sequences where the length is a power of 2. Therefore, I have to zero-pad the input sequences to the a power of 2 (typically the minimal value that is valid) such that their lengths are greater than or equal to the sum of the lengths of the input sequences.

## Usage

       f =: ((#~((+,-)(%_1^i.@#%#))&f(#~-.))1:`0:\)^:(1<#)
       g =: 9 o.<:@+&#{.[:(f%#)[:+@*/,:f@{."1~2^2>.@^.+&#
       1 2 3 4 g 5 6 7 8
    5 16 34 60 61 52 32
       2 4 5 6 1 g 1 2 4 7
    2 8 21 46 61 61 46 7

[1]: http://codegolf.stackexchange.com/a/12475/6710
[2]: https://en.wikipedia.org/wiki/Cooley%E2%80%93Tukey_FFT_algorithm

## Explanation

An explanation for the FFT portion in J is included in my previous [solution][1] to a different challenge.

    9 o.<:@+&#{.[:(f%#)[:+@*/,:f@{."1~2^2>.@^.+&#  Input: A on LHS, B on RHS
                                                #  Get the lengths of A and B
                                              +&   Sum them
                                        2   ^.     Find log base 2 of it
                                         >.@       Find its ceiling
                                      2^           Raise 2 to that power, call it P
                             ,:                    Join A and B as separate rows
                                 {."1~             Pad each row with zeros to length P
                               f@                  Take the FFT of each row
                       [:  */                      Multiply the rows together elementwise
                         +@                        Take the conjugate of each value
                [: f                               Take the FFT of that list
                     #                             Get the length of the list (equal to P)
                    %                              Divide each by P
             #                                     Get the lengths of A and B
           +&                                      Sum them together
        <:@                                        Decrement it
              {.                                   Take that many values from the previous list
    9 o.                                           Take the real part of each value
                                                   Return that list as the result