CODEWITHSUNDEEP
javabig-o
discthrower200
discthrower200

Reputation: 1

Big-O runtime to determine if List contains X and F(X)

I am trying to understand what the Big O would be for the following method.

    for(Integer i : list){
        if(list.contains(-i))
            //doSomething
    }

I know that the contains method is O(n) and that a for loop like that is O(n) as well. Does that make the total for this method O(n * n)?

Upvotes: 0

Views: 1742

Answers (3)

JAMES
JAMES

Reputation: 1

Thus, assuming m and n are two lists, then, the total running time will be n+1m+2m+...+(n-n+1)m.

Upvotes: 0

JAMES
JAMES

Reputation: 1

BUt if you use an iterator on your list, and use the hasNext method, then your total worst case running time will big O(n). Aprroximate formula will be a constant plus n, where n is the if condition. the iterator takes a constant time to return an object, unlike the for loop.

Upvotes: 0

Tim Bender
Tim Bender

Reputation: 20442

Assuming List.contains is O(n), then yes, the whole algorithm is O(n^2).

Upvotes: 1

Related Questions