# Can we say O(n + m) is equivalent to O(n), when m is constant or when n > m

I was solving one of the leetcode problems(Longest Palindrome), where I am

• traversing the whole string(s) to count the frequency of each character
• traversing the array(charFreq) to determine whether the frequency of character is odd and doing operations accordingly.

1. Implementing using array

```   public int longestPalindrome(String s) {

int[] charFreq = new int[58];
for(char sChar : s.toCharArray()){
++charFreq[sChar - 'A'];
}

int charsWithOddFreq = 0;
for(int freq : charFreq){
if((freq & 1) != 0){
charsWithOddFreq++;
}
}

int len = s.length();
return (charsWithOddFreq == 0) ? len : (len - charsWithOddFreq + 1);
}
```

where, `1 <= s.length <= 2000`
`s consists of lowercase and/or uppercase English letters only.`

But, is it correct to say the time complexity of this above program is `O(n + m)`, here `n is the length of the given string(s)` and `m is the size of array taken to store frequency(charFreq)` or is it better to say just `O(n)` as we can neglect the constant factor(m), which is not dependent on the size of the input string and the iteration for each input will always be same(i.e. 58).
In short, is `O(n + m) ~ O(n)` in this case?

2. Implementing same using Map

```public int longestPalindrome(String s) {

Map<Character, Integer> charFreq = new HashMap<>();
for(char sChar : s.toCharArray()) {
charFreq.put(sChar, charFreq.getOrDefault(sChar, 0) + 1);
}

int charWithOddFreq = 0;
for(int val : charFreq.values()) {
if((val & 1) != 0) {
++charWithOddFreq;
}
}

int len = s.length();
return (charWithOddFreq == 0) ? len : (len - charWithOddFreq + 1);
}
```

Using Map, the time complexity should be `O(n + m)`, as m will vary for input string as it is dependent on the input size. But, my question in this case(when using Map) is that can we say `O(n + m)` as `O(n)`, when `n > m`? because according to constraints i.e.
`1 <= s.length <= 2000`
and `s consists of lowercase and/or uppercase English letters only.`
So, length of string(n) > number of lowercase and uppercase letters(m) In short, is `O(n + m) ~ O(n)` in this case too?

A1. Since `m` is a constant (58) in your first algorithm, this is `O(n)` time. This `O(n + constant)` is the same as `O(n)`.

A2. Your second algorithm is also `O(n)` time.

Using Map, the time complexity should be O(n + m), as m will vary for input string as it is dependent on the input size.

You haven’t stated it explicitly, but in this case, `n` is the number of characters in `s`, and `m` is the number of distinct characters in `s`.

Those variable variables `m` and `n` are not independent. In fact `m` will always be less or equal to `n` than `n`.

But `m + n` <= `2n`, and `O(2n)` is the same as `O(n)`. So `O(m + n)` is the same as `O(n)` in this case.

(The above isn’t a rigorous proof … but it should be sufficient to highlight the flaw in your reasoning. If you want a rigorous proof, it is pretty straight forward, albeit tedious.)

Can we say O(n + m) is equivalent to O(n), when m is constant or when n > m

Yes. See above.

Note that the fact that both versions have the same (time) complexity doesn’t mean that their performance will be equivalent.