How to optimize Karatsuba algorithm (using arraylist and java) I was using Karatsuba algorithm to multiply two polynomials and return the coefficients and I am using java, we are asked to use arraylists here, however, my code is too complicated and it takes much longer to run than I expected, can anyone help me with reducing the running time and simplify my code? Thanks a lot!
public static List&lt;Long&gt; smellCosmos(List&lt;Long&gt; a, List&lt;Long&gt; b) {
    int n = a.size();
    int n1 = a.size() / 2;

    List&lt;Long&gt;c = new ArrayList&lt;Long&gt;();

    if (n == 1) {
        c.add(0, a.get(0) * b.get(0));
        return c;
    };

    List&lt;Long&gt;ahigh = new ArrayList&lt;Long&gt;(n1);

    List&lt;Long&gt;alow = new ArrayList&lt;Long&gt;(n1);

    List&lt;Long&gt;amed = new ArrayList&lt;Long&gt;(n1);

    List&lt;Long&gt;bhigh = new ArrayList&lt;Long&gt;(n1);

    List&lt;Long&gt;blow = new ArrayList&lt;Long&gt;(n1);

    List&lt;Long&gt;bmed = new ArrayList&lt;Long&gt;(n1);

    for (int i = 0; i &lt; n1; i++) {
        ahigh.add(a.get(i));
        alow.add(a.get(i + n1));
        amed.add(alow.get(i) + ahigh.get(i));
        bhigh.add(b.get(i));
        blow.add(b.get(i + n1));
        bmed.add(blow.get(i) + bhigh.get(i));
    }

    List&lt;Long&gt;chigh = smellCosmos(ahigh, bhigh);
    List&lt;Long&gt;clow = smellCosmos(alow, blow);
    List&lt;Long&gt;cmed = smellCosmos(amed, bmed);

    for (int j = 0; j &lt; n1; j++)
        c.add(chigh.get(j));

    for (int m = 0; m &lt; cmed.size(); m++)
        c.add(cmed.get(m) - chigh.get(m) - clow.get(m));

    for (int g = cmed.size() - n1; g &lt; clow.size(); g++)
        c.add(clow.get(g));

    for (int i = n1; i &lt; chigh.size(); i++)
        c.set(i, c.get(i) + chigh.get(i));

    for (int i = 0; i &lt; cmed.size() - n1; i++)
        c.set(n1 * 2 + i, c.get(n1 * 2 + i) + clow.get(i));


    return c;

}
```
Reduce running time

Maybe you can use subList to prevent new lists that are basically a copy of a part of the input? This saves a lot of autoboxing (which I assume is the bottle neck, if the algorithm is implemented correctly). You could profile your application to see where most time is spend.

For example:  ahigh = a.subList(0,n1);

You can initialize List c with a size, as you know the length it will be.

Use addAll whenever you can, it will use the faster System.arrayCopy internally if possible.