title: What is the time complexity of this Python code to find string in string
body: <p>What is the time and space complexity of the following code to search a string inside other string, on finding, function should return the index of first occurrence,else -1.</p>
  <p>I assume time complexity is O(m*n) where m is length of haystack and n is length of needle.</p>
  <p>However, i searched for the the memory complexity of python slice and found this answer here - <a href="https://stackoverflow.com/questions/35180377/time-complexity-of-string-slice/35181399">Time complexity of string slice</a> , according to it it is O(n^2).</p>
  <p>So what is the overall time and space complexity of the below function.</p>
  <p>Can we improve it by using <a href="https://docs.python.org/3/library/stdtypes.html#memoryview" rel="nofollow noreferrer">memoryview</a> on haystack.?</p>
  <pre><code>class Solution:
    def strStr(self, haystack, needle):
      if haystack == needle or needle == &quot;&quot;:
          return 0
      
      needle_len = len(needle)
      haystack_len = len(haystack)
      
      for i in range(0, haystack_len - needle_len + 1):
          if needle == haystack[i:i+needle_len]:
              return i
      
      return -1
  </code></pre>