title: Running Time Complexity of my Algorithm - how do i compute this and further optimize the algorithm?
body: <p>I designed a recursive algorithm and wrote it down in Python. When I measure the running time with different parameters, it seems to take exponential time. Furthermore; it takes more than half an hour to end with small numbers such as 50. (I didn't wait until it finishes, but it doesn't seem to finish in a reasonable amount of time, guess it's exponential).</p>
  
  <p>So, I'm curious about the running time complexity of this algorithm. Can someone please help me derive the equation T(n,m)? Or to compute the big-oh?</p>
  
  <p><strong>The algorithm is below:</strong></p>
  
  <pre><code># parameters:
  # search string, the index where we left on the search string, source string, index where we left on the source string,
  # and the indexes array, which keeps track of the indexes found for the characters
  def find(search, searchIndex, source, sourceIndex, indexes):
      found = None
      if searchIndex &lt; len(search): # if we haven't reached the end of the search string yet
          found = False
          while sourceIndex &lt; len(source): # loop thru the source, from where we left off
              if search[searchIndex] == source[sourceIndex]: # if there is a character match
                  # recursively look for the next character of search string 
                  # to see if it can be found in the remaining part of the source string
                  if find(search, searchIndex + 1, source, sourceIndex + 1, indexes):
                      # we have found it
                      found = True # set found = true
                      # if an index for the character in search string has never been found before.
                      # i.e if this is the first time we are finding a place for that current character
                      if indexes[searchIndex] is None:
                          indexes[searchIndex] = sourceIndex # set the index where a match is found
                      # otherwise, if an index has been set before but it's different from what
                      # we are trying to set right now. so that character can be at multiple places.
                      elif indexes[searchIndex] != sourceIndex: 
                          indexes[searchIndex] = -1 # then set it to -1.
              # increment sourceIndex at each iteration so as to look for the remaining part of the source string. 
              sourceIndex = sourceIndex + 1
      return found if found is not None else True
  
  def theCards(N, colors):
      # allcards: a list 1..N of characters where allcards[i] is 'R' if i is a prime number, 'B' otherwise.
      # so in this example where N=7, allcards=['B','R','R','B','R','B','R']
      allcards = ['R' if isPrime(i) else 'B' for i in range(1, N + 1)]
      # indexes is initially None.
      indexes = [None] * len(colors)
  
      find(colors, 0, allcards, 0, indexes)
      return indexes    
  
  if __name__ == "__main__":
      print theCards(7, list("BBB"))
  </code></pre>
  
  <p>I don't know if one has to understand the problem and the algorithm in order to derive the worst-case running time, but here is the problem I attempted to solve:</p>
  
  <p><strong>The Problem:</strong></p>
  
  <p>Given a source string SRC and a search string SEA, find the subsequence SEA in SRC and return the indexes of where each character of SEA was found in SRC. If a character in SEA can be at multiple places in SRC, return -1 for that characters position.</p>
  
  <p>For instance;
  if the source string is BRRBRBR (N=7) and the search string is BBB:
  then the first 'B' in 'BBB' can appear at index 0 in the search string. The second 'B' can be at index 3 of the search string and the last 'B' can be at the 5th position. Furthermore; there exists no other alternatives for the positions of the characters 'BBB', and thus the algorithm returns [0,3,5].</p>
  
  <p>In another case, where the source string is BRRBRB (N=6) and the search string is RBR:
  the first 'R' of 'RBR' can be at position 1 or 2. This leaves only position 3 for 'B' and position 4 for the last 'R'. Then, the first 'R' can be at multiple places, it's place is ambigious. The other two characters, B and R, have only one place. So the algorithm returns [-1,4,5].</p>
  
  <p>The case where the algorithm doesn't finish and take forever is when the source string is ['B', 'R', 'R', 'B', 'R', 'B', 'R', 'B', 'B', 'B', 'R', 'B', 'R', 'B', 'B', 'B', 'R', 'B', 'R', 'B', 'B', 'B', 'R', 'B', 'B', 'B', 'B', 'B', 'R', 'B', 'R', 'B', 'B', 'B', 'B', 'B', 'R', 'B', 'B', 'B', 'R', 'B', 'R', 'B', 'B', 'B', 'R', 'B', 'B', 'B', 'B', 'B', 'R', 'B', 'B', 'B', 'B', 'B'] (N=58)
   and the search string is RBRRBRBBRBRRBBRRBBBRRBBBRR. It should return [-1, -1, -1, -1, -1, -1, -1, -1, 17, 18, 19, 23, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 47, 53 ], but unfortunately it doesn't =(</p>
  
  <p><strong>Optimizations:</strong></p>
  
  <p>I thought of halting the search when the 'indexes' list was completely full of -1s. But that only affects the best-case (or maybe the average-case) but not the worst-case. How can one further optimize this algorithm. I know that there exists a polynomial solution to this problem. </p>
  
  <p>More important than the optimizations, I'm really curious about the T(n,m) equation of the running time, where n and m are the lengths of the source and search strings.</p>
  
  <p>If you were able to read until here, <em>thank you very much!</em> =)</p>
  
  <p><strong>EDIT - IVIad's solution implemented:</strong></p>
  
  <pre><code>def find2(search, source):
      indexes = list()
      last = 0
      for ch in search:
          if last &gt;= len(source):
              break
          while last &lt; len(source) and source[last] != ch:
              last = last + 1
          indexes.append(last)
          last = last + 1
      return indexes
  
  def theCards(N, colors):
      # allcards: a list 1..N of characters where allcards[i] is 'R' if i is a prime number, 'B' otherwise.
      allcards = ['R' if isPrime(i) else 'B' for i in range(1, N + 1)]
  
      indexes = find2(colors, allcards) # find the indexes of the first occurrences of the characters
      colors.reverse() # now reverse both strings
      allcards.reverse()
      # and find the indexes of the first occurrences of the characters, again, but in reversed order
      indexesreversed = find2(colors, allcards)
      indexesreversed.reverse() # reverse back the resulting list of indexes 
      indexesreversed = [len(allcards) - i - 1 for i in indexesreversed] # fix the indices
  
      # return -1 if the indices are different when strings are reversed
      return [indexes[i] + 1 if indexes[i] == indexesreversed[i] else - 1 for i in range(0, len(indexes))]
  
  if __name__ == "__main__":
      print theCards(495, list("RBRRBRBBRBRRBBRRBBBRRBBBRR"))
  </code></pre>