This is my solution in javascript to remove all occurrences of 'b' and 'ac' in a string but I am able to come up with time complexity esp. when removing all occurences for 'ac'. Could someone explain ?
function removeChars(input) {
let result = input;
result = result.replaceAll('b', ''); // tc = O(n) where n is length of string. string of all b's
while(result.indexOf('ac') !== -1) { // number of ac ? what if aacacacc
result = result.replaceAll('ac', ''); // replaceAll has time complexity of O(n)
}
return result; // space ~ O(n)
}
We can consider one of the most special cases: input = aaa...aaaccc...ccc.
Assume the input string has length n, there will be n / 2 occurences for 'ac'. The statement of result = result.replaceAll('ac', ''); will be executed n / 2 times. The time complexity of replaceAll() is O(n), thus the overall time complexity is O(n^2).
The indexOf() method returns the first index at which a given element can be found in the array, or -1 if it is not present, so the worst case will be O(N), and you replaceAll inside the loop so the Big-O is O(N), the total Will O(N^2)
https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/indexOf