Python slice complexity?

Question

What is the time complexity of this short program? I'm thinking it's linear, but then again, in the if statement there's a Python slice. I'm wondering how it would contribute to the complexity:

def count_s(string, sub):

  i = 0
  j =len(sub)-1
  count = 0

  while j < len(string):
      if string[i:j+1] == sub:
          count = count + 1
          j = j + 1
          i = i + 1
      else:
          i = i + 1
          j = j + 1

  return count

Even if the slice were free, the comparison is still a linear-time operation, since it has to compare the two strings character by character. — chepner, Jun 01 '20 at 18:46
Strictly speaking, yes, although it would be fair to express a running time in terms of `n == len(string)` an `m == len(sub)` individually. If `abs(m - n)` is bounded by a constant, the loop only executes a constant number of times. — chepner, Jun 01 '20 at 18:54
@mkrieger1 as in, the Big O complexity of the overall algorithm — kharlezaizen, Jun 01 '20 at 18:56
Yes, but linear/quadratic with the length of `string`? Or with the length of `sub`? Or with the product of `string` and `sub`? — mkrieger1, Jun 01 '20 at 18:58
Does this answer your question? [Big-O of list slicing](https://stackoverflow.com/questions/13203601/big-o-of-list-slicing) — Boris Verkhovskiy, Jun 01 '20 at 19:09
More like O(n + (n-m)*n), or something like that. As `m` grows, the `n-m` term tends from O(n) to O(1). — chepner, Jun 01 '20 at 19:10
@Boris kind of. I get that the slicing would be O(k) where k is the length of the slice, and my question is, would that mean the overall complexity with the while loop factored in would be something like O(k)*O(len(sub))? — kharlezaizen, Jun 01 '20 at 20:00

score 0 · Answer 1 · answered Jun 01 '20 at 19:01

Python's time complexity is O(k) where k is the length of the slice, so your function is O(n * k), which is not linear, yet still not exponential. On the other hand, you could use Python's builtin count function, as such: string.count(sub).

Or, if you're set on using your own code, it could be slimmed down to this for readability's sake:

def count_s(string, sub):
    i = count = 0
    j = len(sub) - 1

    while j < len(string):
        count += string[i:j + 1] == sub
        j += 1
        i += 1

    return count

Python slice complexity?

1 Answers1