Can someone explain to me the runtime of why Perfect Squares is O(sqrt(n))?

Question

Problem

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.

Example 1: Input: n = 12 Output: 3 Explanation: 12 = 4 + 4 + 4

Example 2: Input: n = 13 Output: 2 Explanation: 13 = 4 + 9.

Suggested Solution (BFS)

def numSquares(self, n):
    if n < 2:
        return n
    lst = []
    i = 1
    while i * i <= n:
        lst.append( i * i )
        i += 1
    cnt = 0
    toCheck = {n}
    while toCheck:
        cnt += 1
        temp = set()
        for x in toCheck:
            for y in lst:
                if x == y:
                    return cnt
                if x < y:
                    break
                temp.add(x-y)
        toCheck = temp

    return cnt

How does this particular BFS run in O(sqrt(n))? Because what I am thinking is finding squares take O(sqrt(n)). Because there are 2 for loops, (for y in lst1 takes O(sqrt(n)), for x in toCheck takes O(sqrt(n)), shouldn't it be O(n)??

You probably need to memoize the results to reach O(sqrt(n)) complexity — Reblochon Masque

David Eisenstat David Eisenstat · Accepted Answer · 2018-07-07T03:33:21

The running time is actually Theta(n^(3/2)). According to Legendre's three-square theorem, any integer of the form 4^a (8b + 7) for integers a and b can be written as the sum of four squares but not three. Let n be an integer of this kind. There are Omega(n) numbers less than n that can be written as the sum of three squares, so in the final iteration of the while loop, toCheck has Theta(n) elements, and lst has Theta(n^(1/2)).

Can someone explain to me the runtime of why Perfect Squares is O(sqrt(n))?

1 Answers