Are below statements correct in determining space & time complexity of below code snippets?

• Space complexity for "i" in isCharacterInString() would be O(1) since same variable is kept in every iteration. Would be O(n) only if we kept creating a new "i" variable. So overall this is O(1).

• Space complexity for removeDuplicateLetters() is O(n). filteredString variable grows equally with the size of the input string due to the loop. The bigger/longer the string, the bigger memory it needs.

• Time complexity for isCharacterInString() is O(n) since the for loop grows with the size of the input string.

Can you help me with below questions?

• Is time complexity for removeDuplicateLetters() O(n^2) because it has a nested loop, or O(n) because of relationship between input string and filteredString (as we move through iterations, the string length decreases while filteredString length increases equally)?

• If in removeDuplicateLetters(), filteredString is a random string with random length when the function runs, then would time complexity for removeDuplicateLetters() be O(a * b)?

Code

function isCharacterInString(character, string) {
    for (let i = 0; i < string.length; i  ) {
        if (character === string[i]) {
            return true;
        }
    }
    return false;
}

function removeDuplicateLetters(string) {
    let filteredString = '';
    for (let i = 0; i < string.length; i  ) {
        if (!isCharacterInString(string[i], filteredString)) {
            filteredString  = string[i];
        }
    }
    return filteredString;
}

CodePudding user response：

Is time complexity for removeDuplicateLetters() O(n^2) because it has a nested loop, or O(n) …

Yes, in general it's quadratic because of the nested loop, assuming the if condition is always true and filteredString always grows, for an average length of O(n) (where n is the input string.length). However, you could argue that it's rather O(n*m) where m is the number of different characters in the string - making this linear iff you pass a string consisting of the same character repeated.

But if we don't know anything about the character distribution in the input, we have to assume the worst case n - or maybe min(n, |Σ|) where |Σ| is the size of the alphabet, which usually is assumed to be arbitrarily large but finite. So you could in theory argue that m is O(1), but with a huge constant factor - better don't do that in practice.

CodePudding user response：

Worst case removeDuplicateLetters is going to be O(n^2) and isCharacterInString is O(n), space complexity would not matter here but it will be worst case simliar to the the length of string you provided in param to removeDuplicateLetters. This was the answer specific to your question. There are better ways you can get rid of dups from a string.

CodePudding user response：

Is time complexity for removeDuplicateLetters() O(n^2)

Imagine the worst case. This is when there are no duplicate letters. Take for example abcde.

We end up doing

• isCharacterInString('a', ''), which loops 0 times
• isCharacterInString('b', 'a'), which loops 1 times
• isCharacterInString('c', 'ab'), which loops 2 times
• isCharacterInString('d', 'abc'), which loops 3 times
• isCharacterInString('e', 'abcd'), which loops 4 times

In the worse case, the loop body in removeDuplicateLetters is executed n times, and the loop body in isCharacterInString is executed (n-1) (n-2) ... 1 0 = n(n-1)/2 times.

Assuming the concatenation is O(1)^[1], this means that removeDuplicateLetters is O(n^2).

[Upd: Bergi raises a good point about the alphabet being a limiting factor. O() evaluates how an algorithm scales as the size of the inputs grows. In other words, it answers what happens when n is very large. And there's a point at which n is going to exceed the number of symbols in the alphabet. So it's really O(n*s), where s is the number of symbols in the alphabet. If we don't care about what happens when the size of the alphabet grows, s is effectively constant, giving us O(n) instead of O(n^2). I think O(n) is too misleading, though. O(n*s) would be acceptable, and someone is free to consider it O(n) if s is much smaller than n, or O(n^2) if s is very large.]

---

If in removeDuplicateLetters(), filteredString is a random string with random length when the function runs, then would time complexity for removeDuplicateLetters() be O(a * b)?

Not enough information to answer. It depends on whether the algorithm still changes filteredString, and on whether the initial length of filteredString a parameter of removeDuplicateLetters or constant.

---

1. Without preallocation, it's O(n) to do n additions at best. This is effectively O(1) for our purposes, and it's called "amortized O(1)".