CODEWITHSUNDEEP
javatime-complexitybig-o
user3437460
user3437460

Reputation: 17454

Why does nested loop with list.add gives O(n^4) time complexity?

I came across this question for the Big O time complexity of this code snippet: It is guaranteed that the time complexity for the following code is 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?

My Question: Why is it O(n^4) instead of O(n^3)?

Upvotes: 3

Views: 231

Answers (2)

pr0p
pr0p

Reputation: 2358

list.contains(i*j) happens in O(n^2) as i and j are dependents on n ( if linear search is used ). Basically it will be 2 loops in O(n) nested and an operation of of O(n^2) inside the nested loop and hence O(n^4).

Upvotes: 0

k5_
k5_

Reputation: 5558

list has about n^2/2 entries[*], so the lookup list.contains(i*j) is O(n^2) not O(n)

*: some less because duplicates are not added, but i guess enough to count as n^2

Upvotes: 7

Related Questions