What is the time complexity of this BFS algorithm?

Question

I looked at LeetCode question 270. Perfext Squares:

Given an integer n, return the least number of perfect square numbers that sum to n.

A perfect square 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.>

Example 1:

Input: n = 12
Output: 3 
Explanation: 12 = 4 + 4 + 4.

I solved it using the following algorithm:

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 < square:
                    break
                tempQueue.add(node-square)
        queue = tempQueue
        step += 1

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.

Question

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.

Answer 1

If you think about what you're doing, you can imagine that you're doing a breadth-first search over a graph with n + 1 nodes (all the natural numbers between 0 and n, inclusive) and some number of edges m, which we'll determine later on. Your graph is essentially represented as an adjacency list, since at each point you iterate over all the outgoing edges (squares less than or equal to your number) and stop as soon as you consider a square that's too large. As a result, the runtime will be O(n + m), and all we have to do now is work out what m is.

(There's another cost here in computing all the square roots up to and including n, but that takes time O(n^1/2), which is dominated by the O(n) term.)

If you think about it, the number of outgoing edges from each number k will be given by the number of perfect squares less than or equal to k. That value is equal to ⌊√k⌋ (check this for a few examples - it works!). This means that the total number of edges is upper-bounded by

√0 + √1 + √2 + ... + √n

We can show that this sum is Θ(n^3/2). First, we'll upper-bound this sum at O(n^3/2), which we can do by noting that

√0 + √1 + √2 + ... + √n

≤ √n + √n + √ n + ... + √n (n+1) times

= (n + 1)√n

= O(n^3/2).

To lower-bound this at Ω(n^3/2), notice that

√0 + √1 + √2 + ... + √ n

≥ √(n/2) + √(n/2 + 1) + ... + √(n) (drop the first half of the terms)

≥ √(n/2) + √(n/2) + ... + √(n/2)

= (n / 2)√(n / 2)

= Ω(n^3/2).

So overall, the number of edges is Θ(n^3/2), so using a regular analysis of breadth-first search we can see that the runtime will be O(n^3/2).

This bound is likely not tight, because this assumes that you visit every single node and every single edge, which isn't going to happen. However, I'm not sure how to tighten things much beyond this.

As a note - this would be a great place to use A* search instead of breadth-first search, since you can fairly easily come up with heuristics to underestimate the remaining total distance (say, take the number and divide it by the largest perfect square less than it). That would cause the search to focus on extremely promising paths that jump rapidly toward 0 before less-good paths, like, say, always taking steps of size one.

Hope this helps!

Answer 2

Some observations:

1. The number of squares up to n is √n (floored to the nearest integer)
2. After the first iteration of the while loop, tempQueue will have √n entries
3. tempQueue can never have more than n entries, since all these values are positive, less than n and unique.
4. Every natural number can be written as the sum of four integer squares. So that means your BFS algorithm's while loop will iterate at the most 4 times. If the return statement did not get executed during any of the first 3 iterations, it is guaranteed it will in the 4^th.
5. Every statement (except for the initialisation of squares) runs in constant time, even the call to .add().
6. The initialisation of squares has a list comprehension loop that has √n iterations, and range runs in constant time, so that initialisation has a time complexity of O(√n).

Now we can set a ceiling to the number of times the if node-square == 0 statement is executed (or any other statement in the innermost loop's body):

        1⋅√n + √n⋅√n + n⋅√n + n⋅√n

Each of the 4 terms corresponds to an iteration of the while loop. The left factor of each product corresponds to the maximum size of queue in that particular iteration, and the factor at the right corresponds to the size of squares (always the same). This simplifies to:

        √n + n + 2n^3⁄2

In terms of time complexity this is:

        O(n^3⁄2)

This is the worst case time complexity. When the while loop only has to iterate twice, it is O(n), and when only once (when n is a square), it is O(√n).