title: What is the time complexity of this BFS algorithm?
body: <p>I looked at LeetCode question <a href="https://leetcode.com/problems/perfect-squares/" rel="nofollow noreferrer">270. Perfext Squares</a>:</p>
  <blockquote>
  <p>Given an integer n, return the least number of perfect square numbers that sum to n.</p>
  <p>A <strong>perfect square</strong> is an integer that is the square of an integer; in other words, it is the product of some integer with itself. For example, 1, 4, 9, and 16 are perfect squares while 3 and 11 are not.&gt;</p>
  <h3>Example 1:</h3>
  <pre><code>Input: n = 12
  Output: 3 
  Explanation: 12 = 4 + 4 + 4.
  </code></pre>
  </blockquote>
  <p>I solved it using the following algorithm:</p>
  <pre class="lang-py prettyprint-override"><code>def numSquares(n):
      squares = [i**2 for i in range(1, int(n**0.5)+1)]
      step = 1
      queue = {n}
      while queue:
          tempQueue = set()
          for node in queue:
              for square in squares:
                  if node-square == 0:
                      return step
                  if node &lt; square:
                      break
                  tempQueue.add(node-square)
          queue = tempQueue
          step += 1
  </code></pre>
  <p>It basically tries to go from goal number to 0 by subtracting each possible number, which are : [1 , 4, 9, .. sqrt(n)] and then does the same work for each of the numbers obtained.</p>
  <h1>Question</h1>
  <p>What is the time complexity of this algorithm? The branching in every level is sqrt(n) times, but some branches are destined to end early... which makes me wonder how to derive the time complexity.</p>