educative.io

Educative

About Happy number question description

Hi,
I’m trying to understand what these mean.

  1. N1 < 81MN1<81M
  2. As we know M = log(N+1) <---- why it’s M = log(N+1)?
  3. Therefore: N1 < 81 * log(N+1) => N1 = O(logN)

Can you please let me know how this time complexity is O(log N)?

Hi @Mingyu_Jeon!
As we assumed the number of digits as ‘M’ so M=log(N+1) is the formula to find the number of digits of a number.
The complexity is O(log N) because we are processing each digit in the number, and the number of digits of each number is given by log N.