java - 递归方法的大 O 复杂度

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);
       }
    }
}