title: How does these two methods have different time complexity in Python?
body: <p>I am trying to solve the <a href="https://leetcode.com/problems/word-search" rel="nofollow noreferrer">Leetcode word search problem</a> .</p>
  <p>I have two solutions which to me is identical although one of them returns in Time Limit Exceeded.</p>
  <p>I read all resources around this and could not understand what is happening behind the scene.</p>
  <p>Solution 1 with optimised time complexity:</p>
  <pre><code>class Solution(object):
      def bfs(self, position, visited, board, word):
          # print(position)
          if not word:
              return True
  
          destination = [(-1,0), (1,0), (0,1), (0,-1)]
          res = False
          for x,y in destination:
              new_postion_x, new_postion_y = position[0] + x, position[1] + y
              if (0&lt;= new_postion_x &lt; len(board)) and (0 &lt;= new_postion_y &lt; len(board[0])) and (new_postion_x, new_postion_y) not in visited:
                  if board[new_postion_x][new_postion_y] == word[0]:
                      new_visited = visited.copy()
                      new_visited[(new_postion_x,new_postion_y)] = 1
                      res = res or self.bfs((new_postion_x, new_postion_y), new_visited, board, word[1:])
          return res
  
      def exist(self, board, word):
          for i in xrange(len(board)):
              for j in xrange(len(board[0])):
                  if board[i][j] == word[0]:
                      t = self.bfs((i,j), {(i,j): 1}, board, word[1:])
                      if t:
                          return True
          return False
  </code></pre>
  <p>Solution two which returns TLE on execution for large input:</p>
  <pre><code>class Solution(object):
      def bfs(self, position, visited, board, word):
          print(position)
          if not word:
              return True
  
          destination = [(-1,0), (1,0), (0,1), (0,-1)]
          res = False
          for x,y in destination:
              new_postion_x, new_postion_y = position[0] + x, position[1] + y
              if (0&lt;= new_postion_x &lt; len(board)) and (0 &lt;= new_postion_y &lt; len(board[0])) and (new_postion_x, new_postion_y) not in visited:
                  if board[new_postion_x][new_postion_y] == word[0]:
                      new_visited = visited.copy()
                      new_visited[(new_postion_x,new_postion_y)] = 1
                      t = self.bfs((new_postion_x, new_postion_y), new_visited, board, word[1:])
                      res = res or t
          return res
  
      def exist(self, board, word):
          for i in xrange(len(board)):
              for j in xrange(len(board[0])):
                  if board[i][j] == word[0]:
                      t = self.bfs((i,j), {(i,j): 1}, board, word[1:])
                      if t:
                          return True
          return False
  </code></pre>