0% completed
I am also failing to understand the time complexity of the algo. I understand th...
aj
Jun 16, 2022
I am also failing to understand the time complexity of the algo. I understand that creating the map is O(M) and the window for loop is O(N). How is total complexity O(N+M) because what about the inner while loop. Take this e.g. str = 'aaaaaabc', pattern = 'bc'. The while loop will run for a substantial time. In worst case of O(N-M) right? Then can we just ignore this altogether?
0
0
Comments
aj 3 years ago
systemdesign Could you please comment if my understanding is correct or not?
Design Gurus3 years ago
No, the complexity can't be O(N-M) in the worst case.
For the example input you mentioned, try seeing how many iterations the 'for' loop does. It will have to do 'N' iterations as it has to iterate the whole string.
Similarly, try seeing how many iterations the 'while...
aj 3 years ago
Hi, yes I agree the 'for' loop does N iterations. That part was clear to me.
But I revisited the 'inner while loop' again and I see that for the example I shared it will run for all the 'a' chars until it reaches 'b' which is N - M times. N is 8, M is 2. Remaining char...
aj 3 years ago
Also, I do NOT mean that the final complexity is O(N-M). O(N-M) could be the complexity of the 'inner while loop' is what I meant.
My question is about - if the complexity of the 'inner while loop' has been considered for the final complexity of the algo or NOT. And ...
Design Gurus3 years ago
Yes, you are right, the complexity of the inner 'while' loop will be O(N-M).
So, as the 'for' loop iterates 'N' times, the overall complexity of the function will be:
O(N + (N-M) => O(2N - M)
We can further simplify this:
As 'M' will never be bigger than N, which ...
Matt 3 years ago
Nice explanation. It may also be worth noting the string slicing method is an O(n) operation in itself in some languages. Still all boils down to an overall of O(n) though.
On this page