CODEWITHSUNDEEP
pythonalgorithm
Barton Dong
Barton Dong

Reputation: 127

What is the time and space complexity of the count string function

def count(substring, string):
    """
    >>> count("bc","abcabcabc")
    3
    """
    counter = 0
    for i in range(len(string) - len(substring) + 1):
        counter += string.startswith(substring, i)

    return counter

This is a function to count the number of recurrence of a substring in the base string. I think the time complexity is O(n) since I only iterate the string once. I think the space complexity is O(n) as well because I increment the counter in the loop N times. Can someone tell me if I am right or wrong?

Upvotes: 0

Views: 1391

Answers (1)

Kelly Joyner
Kelly Joyner

Reputation: 143

The time complexity is O(nm) where n=len(s) and m=len(t) for the reason you provide, but incrementing counter doesn't cause it take up more space, so the space complexity of this function is O(1). No matter how long the input string is, you still only store a single variable, count.

[Edited to correct egregious error pointed out by poster]

Upvotes: 2

Related Questions