How to avoid time complexity O(n^2)?

Question

I have this following piece of code:

for(ArticleBasketInBean basketBean : bean.getBasket()) {
    for(ArticleDTO article : dto.getArticleList()) {
        if(basketBean.getArticleReference().equals(article.getArticleReference())) {
            article.setAddedToBasket(true);
        }
    }
}

Clearly the time complexity of the above operation is O(n^2). For this case articleReference is unique. So the list returned by bean.getBasket() has no duplicate articleReference, also this is true for the list returned by dto.getArticleList().

I want to avoid this nested iteration and want to write faster code. How can I do that?

Answer 1

Use java.util.HashSet to cache one of the sets of references, assuming the sets are not TOO large, of course. With a good hash function, this should bring you back to O(n).