java - 再帰的方法のBigOの複雑さ

Question

これは再帰的に行われる一連の数値のJava順列であり、その大きなOの複雑さが何であるかを調べる必要があります。ネストされたループのためにO（N ^ 2）になると想定しましたが、友人は再帰メソッドの動作が異なるとコメントしました。どんな助けでも大歓迎です

public void permuteRec(ArrayList<Integer> list1, ArrayList<Integer> list2)
{
    if (list1.isEmpty())
    {
        if (computeDistance(list2) < distance)
        {
            path = list2;
            recomputeDistance();
        }
    }
}
else
{
    for (int i = 0; i < list1.size(); i++)
    {
       ArrayList<Integer> tmp2 = new ArrayList<Integer>();
       for(int k = 0; k < list2.size(); k++)
       tmp2.add(list2.get(k));
       tmp2.add(list1.get(i));
       ArrayList<Integer> tmp1 = new ArrayList<Integer>();
       for(int k = 0; k < list1.size(); k++)
       {
           tmp1.add(list1.get(k));
           tmp1.remove(i);
           permuteRec(tmp1, tmp2);
       }
    }
}