CODEWITHSUNDEEP
algorithmbig-o
CaptainForge
CaptainForge

Reputation: 1395

Are nested for loops always O(n^2)?

I'm struggling coming up with a complexity for this code (this isn't a homework problem, I'm just trying to understand this concept):

public static boolean boxesHaveItem(List<Box> boxes, Item object) {
    for (Box box : boxes) {
        for (Item item : box.getItems()) {
            if (item.equals(object)) {
                return true;
            }
        }
    }
    return false;
}

Because there are nested for loops, your instict would be O(n^2), but that doesn't make sense because the number of items in a box is unrelated to the number of boxes I'm passing to this method.

Maybe O(mn), where m = average # of items in a box, n = # of boxes?

I was thinking O(n) would be best, where n is the total # of items in all of the boxes passed to the function, but that's kinda weird because they aren't directly passed to the function.

Upvotes: 4

Views: 18147

Answers (1)

Zabuzard
Zabuzard

Reputation: 25903

You have multiple choices here. When talking about complexities you should choose a dependency which is useful for your audience.

The method clearly depends on the amount of items, it yields Theta(|items|). So if n is the amount of items, then you have Theta(n), that is absolutely correct.

If there is a dependency from items to boxes, e.g. a box can maximally contain 5 items, then you can also express the complexity depended on the amount of boxes. It then obviously also yields Theta(|boxes|).

If there is no dependency then you can not express the complexity with the amount of boxes since it then does not depend on it.

Just choose whatever you find most appropriate for your audience.

"Are nested for-loops always O(n^2)?"

To your other question, the answer is no. They aren't always O(n^2). You can easily create a situation where one of the loops affects the iterations of the other, yielding a different complexity.

A small constructed example:

for (int i = 0; i < n; i++) {
    for (int j = i; j < i + 5 && j < amount; j++) {
        ...
    }
}

The loop may, at first glance, look like O(n^2) but the inner loop maximally creates 5 iterations for every iteration of the outer loop. So we receive only 5 * n iterations in total, not something like n^2. The complexity thus is O(n).

Upvotes: 18

Related Questions