I have written a Happy number program using an array, help me how to calculate Time Complexity? Any number will be called a happy number if, after repeatedly replacing it with a number equal to the sum of the square of all of its digits, leads us to number ‘1’. All other (not-happy) numbers will never reach ‘1’. Instead, they will be stuck in a cycle of numbers which does not include ‘1’.
def happy(num):
ls = []
result = 0
while True:
result = sqr_digits(num)
if result == 1:
return True
elif result in ls:
return False # not happy
else:
ls.append(result)
num = result
def sqr_digits(num):
result = 0
while(num > 0):
digit = num % 10
result += digit ** 2
num //= 10
return result
num = 145
print(happy(num))
[Note: While answering the question, I forgot that your code is using digit^2, but I've just provided the solution based on digit. The complexity calculation mechanism is same. If you read the answer, you can easily find out the complexity for digit^2 by yourself. I'll update the answer, when I get sometime. Hope you wouldn't mind]
Well, if there is a number n(base 10), then it can have at most log10(n) + 1 digits. I hope, i would not have explain it...just google it how many digits in a 10 based number and how to find it using log.
Now, let's explain the complexity of the provided algo:
The algo will only be stopped when the sum turns into a single digit.
So, we can calculate the number of digits, we've to add and that'll be the complexity ultimately.
Exactly calculate the complexity of this algo is not possible, but we can calcuate the complexity of worst case...what would could be max number with 3 digits, of course 999, so we'll always consider d nines in a d digits number.
1st iteration:: no of digits, d1 = log10(n) + 1, and n1 = d1*10, (originally d1*9 in worst
case, but we're taking much worse and the reason is to calculate complexity properly)
2nd iteration:: no of digits, d2 = log10(n1) + 1 and n2 = d2*10
= log10(d1*10) + 1
= log10(d1) + 1 + 1 (cause, log(a*b) = log(a)+log(b))
= log10(log10(n) + 1) + 1 + 1
3rd iteration:: no of digits, d3 = log10(log10(log10(n)+1)+1) + 1 + 1 + 1
...
...
I guess, you can see where this is going. The total digits number can be written as:
total digits = d1 + d2 + d3 + ....
By removing the 1 inside log's(for simplification) we can write simply:
total digits = log10(n) + 1 + log10(log10(n)) + 2 + log10(log10(log10(n))) + 3 + ...
but, log10(n) + 1 >>> log10(log10(n)) + 2
So, we can see that the ultimate complexity is determined by log10(n). The ultimate complexity would be:
complexity = c * log10(n) // here is "c" a constant such that c * log10(n) > total digits
which
we can say O(log10(n))
I hope you've understood the concept properly...