What is the Run Time Complexity and Space Complexity of this solution in terms of Big O?

user_9520622 0
Viewed 100

I believe the space complexity would just be O(n) since the set is the only one that is stored throughout the program and the list is recalculated each time. I'm not sure if the time complexity would be O(n^2) because there is a while loop and inside there is a for loop or if it is something different because the while loop can just keep running if n is never 1 or in the set.

def isHappy(self,n):
        seen = set()
        while True:
            if n not in seen:
                seen.add(n)
                n = sum([int(x) * int(x) for x in str(n)])
                if n == 1:
                    return True
            else:
                return False
big-o python
2 Answers

EDIT:

The previous statement about average time complexity was incorrect, as it did not take the complexity of the summing of squares of n's decimal digits into account.

Forgive me in advance for the lack of mathematical formatting. There's no easy way to do that in StackOverflow posts.

The short answer is that your solution will not enter an infinite loop, and it does indeed have O(n) space complexity and O(n**2) time complexity.

Here's the long answer:

Let f(n) denote the result of summing the squares of n's decimal digits, as is being done inside the while loop. If n has four or more digits, then f(n) is guaranteed to have fewer digits than n, as

f(9999) == 4 * 9**2 == 324

, and the difference between 10**k - 1 and f(10**k - 1) increases as k increases. So it takes, at most, log10(n) iterations of the loop to get to a three digit number for an n with four or more digits. And as

f(999) == 3 * 9**2 == 243

, no matter how many times you apply n = f(n) to an n with three or fewer digits, the result will also have three or fewer digits. There are only 1000 nonnegative integers with three or fewer digits, so by the Pigeonhole Principle, f(n) will either equal one or already be contained in the set after at most 1001 iterations. In total, that's no greater than log10(n) + 1001 iterations of the loop, where in this case n refers to the original value of the function argument.

For a set s, insertion and membership testing are both O(len(s)) in the worst case. Since the set can contain only as many elements as there are past iterations,

len(s) <= log10(n) + 1001.

And log10(n) + 1001 is O(n) (but not O(log(n)), since complexity is in terms of the size of the input (the number of digits), not the input itself). And since, during a given iteration, n either has fewer than its original number of digits or fewer than four digits, the summing of squares is also O(n) in the number of digits. In total, that's O(n) iterations that are O(n) each, for a total worst-case time complexity of O(n**2).

As explained above, you're guaranteed to reach a three-digit number eventually no matter how large n is, so you can actually replace the set with a list of 1000 bools. Then the solution would have O(1) space complexity.

user_65266930

The best case scenario is O(1) suppose if the program gets answer in the first attempt and the worst case scenario might be O(n^2) since the loop iterates over itself again and again but if you want a more precise answer than you can consider adding a new constant which will represent the following loop

sum([int(x) * int(x) for x in str(n)])

lets represent this loop with a constant r then the worst case complexity will become O(n^2 + r)

user_101518470
Related