CODEWITHSUNDEEP
java
user12166774
user12166774

Reputation:

Complexity for a limited for loop iterations

I have a quick question about Complexity. I have this code in Java:

pairs is a HashMap that contains an Integer as a key, and it's frequency in a Collection<Integer> as a value. So : 

pairs = new Hashmap<Integer number, Integer numberFrequency>()

Then I want to find the matching Pairs (a,b) that verify a + b == targetSum. 

for (int i = 0; i < pairs.getCapacity(); i++) { // Complexity : O(n)
    if (pairs.containsKey(targetSum - i) && targetSum - i == i) {
        for (int j = 1; j < pairs.get(targetSum - i); j++) {
            collection.add(new MatchingPair(targetSum - i, i));
        }
    }
}

I know that the complexity of the first For loop is O(n), but the second for Loop it only loops a small amount of times, which is the frequency of the number-1, do we still count it as O(n) so this whole portion of code will be O(n^2) ? If it is does someone have any alternative to just make it O(n) ?

Upvotes: 1

Views: 44

Answers (2)

Kemar Gooden
Kemar Gooden

Reputation: 46

Its O(n) if 'pairs.getCapacity()' or 'pairs.get(targetSum - i)' is a constant you know before hand. Else, two loops, one nested in the other, is generally O(n^2).

Upvotes: 1

heyhooo
heyhooo

Reputation: 82

You can consider that for the wors case your complexity is O(n2)

Upvotes: 0

Related Questions