educative.io

Educative

Why is the time complexity O(log(n))?

Courses
, ,
#1

How was this determined?

for example if the number N = 4 we have

4^2 = 16
1^2 + 6^2 = 38
3^2 + 8^2 = 56
…

it actually takes 7 operations to determine that 4 is not a happy number.

This is a little difficult to determine the time complexity, no? How did we decide on this?

2 Likes
#2

hey @Will_Wright!

Thanks for pointing this out. We maintain track of two values using a slow pointer and a fast pointer. The slow runner advances one number at each step, while the fast runner advances two numbers. We detect if there is any cycle by comparing the two values and checking if the fast runner has indeed reached number one.
The time complexity for the solution shown above is O(\log n) O(logn). However, since there were two pointers, the cost is O(\log n + \log n) O(logn+logn) , that is, O(\log n) O(long).
We hope Educative has inspired you to further your learning. :blush:
.

#3

Hey,

The time complexity for the solution shown above is O(\log n) O(logn)
I’m still not sure why is it O(log(n))?!

#4

Hey @Waleed_Yaser ,

I hope you are doing well,

If there are no cycles, the time complexity for the runner would be O(logn) to reach the end. Since we have two runners, the time complexity would be O(2.logn) which is O(logn). If there are k cycles present, it would take k-1 steps for the fast runner to reach the slow runner. This is done in constant time. So the overall complexity turns out to be O(logn).

As always, we appreciate our valued users reaching out to us. Therefore, please write to us if you have any further queries, concerns, or suggestions in general.

We hope you enjoy your experience with us at Educative! Happy learning!

#5

Hello. Since I couldn’t find any proper answer to this question, I searched on the web.

Here is what i could find as a satisfactory explanation from leetcode discussion on this problem -

The time complexity of this implementation is O(klog(n))
n is the input number
k is the number of iterations required to determine whether the number is happy.
Each iteration of the while loop involves calculating the sum of the squares of the digits in n, which takes log(n) time (since there are log(n) digits in the number n, and each digit requires a constant amount of time to square and sum). Therefore, the time complexity of each iteration of the while loop is O(log(n))
Overall, the while loop runs at most k times, so the total time complexity of the algorithm is O(klog(n))

The space complexity of this implementation is also O(k), since the set of visited numbers can contain at most k numbers. Note that the maximum value of k is unbounded, so the space complexity could potentially be very large for very large input numbers.

In practice, however, the value of k is typically quite small for most input numbers, so the actual time and space complexity of this implementation is usually much lower than the worst-case complexity.