'What is the time complexity of this python function which includes slice operations?
I am learning python slice operations and I decided to write a simple function that iterates through a string with a window of size k and adds the window to the dictionary along with its frequency. So for example if the string input is "abab" and k is 2, the dictionary will contain "ab:2" and "ba:1".
I am confused what will be the time complexity of this function:
In the code, s is input string and k is window size.
def test_func(s, k):
d = {}
for i in range(len(s) - k + 1):
sub_str = s[i:i+k]
if sub_str in d:
d[sub_str] += 1
else:
d[sub_str] = 1
return d
I am thinking that time complexity of it will be O(n * k) and space complexity of it will be O(n) where n is size of list and k is size of window but I am not sure if it is right. Can you please review the function and let me know if my analysis is correct? Thank you!
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
| Solution | Source |
|---|
