educative.io

Educative

I do not understand the Time Complexity of this solution

Could someone please explain why the Time Complexity of this solution is O(2×logn)?


Course: https://www.educative.io/courses/grokking-coding-interview-patterns-python
Lesson: Solution: Happy Number - Grokking Coding Interview Patterns in Python

1 Like

Hello John,

The time complexity for any set operation is O(log n) in Python.
In the solution we’re accessing the numbers stored in a set. The fast pointer will reach 1 at the end of the code, and since slow pointer is half steps back, it’ll be in the middle of the set. For both pointers, the time complexity will be O(log n).
Time complexity for one pointer : O(1 x log n)
In our case, we have two pointers in total.
Time complexity for two pointer: O(2 x log n)
As, constants do not matter in complexities, in this case the time complexity will become O(log n).

You are referring to the naive approach, which uses a set. I am referring to the optimal approach, which uses a fast and a slow pointer instead.

The best lead I have is quoting from this stack overflow post,
“the number of digits of a base 10 number is given by it’s value (N) taken to the logarithm at base 10, rounded down. So for example, 1023 would have floor(log10(1023)) digits, which is 3. So yes, the N is the value of the number. the log in time complexity indicates a logarithm, not specifically that of base 2 or base e.”

@John-Michael_Bradley I think what Syed is trying to say is that in the case of the optimal approach also, if the result is True (is a Happy number), the complexity is logn. This is because to reach 1, the fast pointer will reach 1 in logn and the slow pointer will still be at the middle with logn. So total complexity is logn.

But I have another question, in the case when it is not a happy number, then there is a chance that the fast and slow pointer does not meet easily at one point to the same number(even after 1 complete iteration of all the numbers slow pointer - O(n)), then the complexity is worse than the naive approach (O(n)), isnt it ? Please let me know what you guys think ?


Course: Grokking Coding Interview Patterns in Python - Learn Interactively
Lesson: Solution: Happy Number - Grokking Coding Interview Patterns in Python

Hello @Sabyasachi_Ghosal,

The time complexity of the code is O(log(n)), where n is the input number. This is because the number of iterations in the while loop is proportional to the number of digits in n. The logarithmic time complexity is because each iteration reduces the size of the input by a factor of 10. Even in the worst case, when n is not a happy number at each cycle, the faster runner will get one step closer to the slower runner. When the faster runner is one step behind the slower runner, they will meet on the next step. If there are “t” numbers in the cycle, and they started “t-1” places apart, the fastest runner will need “t-1” steps to reach the slower runner, and this is a constant value. Hence, the most significant task remains to find the next value for the starting n, with a time complexity of O(logn).

Happy Learning!

1 Like

Hi @Adeel_Qayyum , could you clarify why each iteration reduces the size of the input by a factor of 10? In the example with 4 as the start, the path is 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4. The size of the input seems to go from 1 → 2 → 2 → 2 → 2 → 3 → 2 → 2 → 1 instead of reducing by a factor of 10 each iteration.

1 Like

Hi @Sabyasachi_Ghosal and @Rony_Krell!

The worst case time complexity of this algorithm is given by the case of a non-happy number, since it gets stuck in a cycle, whereas a happy number quickly converges to 1. Let’s first calculate the time complexity of the Sum Digits function. Since we are calculating the sum of all digits in a number, the time complexity of this function is O(log n), because the number of digits in the number n is log n.

To estimate the count of numbers in a cycle, let’s consider the following two cases:

1. Numbers with three digits: The largest three-digit number is 999. The sum of the squares of its digits is 243. Therefore, for three-digit numbers, no number in the cycle can go beyond 243. Therefore, the time complexity in this case is given as O(243*3), where 243 is the maximum count of numbers in a cycle and 3 is the number of digits in a three-digit number. This is why the time complexity in the case of numbers with three digits comes out to be O(1).

2. Numbers with more than three digits: Any number with more than three digits will lose at least one digit at every step until it becomes a three-digit number. For example, the first four-digit number that we can get in the cycle is 1053, which is the sum of the square of the digits in 9999999999999. Therefore, the time complexity of any number with more than three digits can be expressed as O(log n + log log n + log log log n + …). Since O(log n) is the dominating term, we can write the time complexity as O(log n).

Therefore, the total time complexity comes out to be O(1 + log n), which is O(log n).

1 Like