为什么嵌套循环与list.add给出O(n ^ 4)时间复杂度？

Question

我遇到了这个代码片段的Big O时间复杂度的问题:保证以下代码的时间复杂度为O(n ^ 4).

ArrayList<Integer> list = new ArrayList<Integer>();

for(int i = n; i>=1; i--)           //n 
    for(int j = 1; j<=i; j++)       //n     
        if(!list.contains(i*j))     //n?    
            list.add(i*j);          //1?

我的问题:为什么是O(n ^ 4)而不是O(n ^ 3)？

Answer 1

list大约有n^2/2项[*],所以查找list.contains(i*j)是O(n^2)不是O(n)

*:少了一些,因为没有添加重复项,但我想这足以算作 n^2