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!

CodePudding user response：

Time and space should both be O(n*k).

Looking up a dictionary key of size k is O(k) because you have to hash k, which requires reading all the characters of k. While we often treat dictionary and set lookup as amortized constant time, I don't think we can use that simplification when the dictionary key size is one of the parameters.

Since you do these lookups O(n) times, the time complexity is O(n*k).

Since all the keys have to be stored in the dictionary, and the worst case is that there are no duplicate slices, the dictionary may have to contain n*k keys.