I understand that this is not the best optimized code for leetcode problem 202 Happy Number but I am trying to figure out what the Big O of this because of the conditional while loop. Ofc if n starts out as 0-4, it would be O(1). Thanks for the help in advance!

/**
 * @param {number} n
 * @return {boolean}
 */

var isHappy = function(n) {
    /* pseudocode
    - n is input
    - while loop if num is greater than 1
    - turn number to string 
    - split the string
    - map to an array
    - add all numbers' squares
    - if num is 1, break and return true
    - if not loop 
    */
    
    // check for definite false cases
    if (n === 1) {
            return true;
        }
    else if (n === 0|| n === 2 || n === 3 || n === 4) {
        return false;
        }
    
    while (n > 1) {
        // split and turn to string
        n = n.toString().split("");
        console.log(n);
        
        // map to arr
        //let tempArr = n.map(n);
        console.log("n: "   n);
        
        // add all nums squares
        let tempNum = 0;
        n.forEach(e => {
            tempNum  = (e**2);
            console.log("adding ", e**2);
        });
        
        // change n to sum and reset tempNum
        n = tempNum;
        tempNum = 0;
        
        // check conditions for true/false
        if (n === 1) {
            return true;
        }
        else if (n === 0|| n === 2 || n === 3 || n === 4) {
        return false;
        }
    }
};

Accepted result on Leetcode:

Runtime: 321 ms, faster than 5.03% of JavaScript online submissions for Happy Number.

Memory Usage: 50.6 MB, less than 5.13% of JavaScript online submissions for Happy Number.

CodePudding user response：

With big-O, you're trying to find the worst-case scenario - you may get lucky and hit O(1), but that won't always be the case.

Your worst case would occur when n > 4 - the code goes to the while loop. Based on the section n.forEach.., your worst case is O(n).

EDIT:

So looking a bit more closely at the code, you cast n to a string and then split up the values. So in terms of the big-O notation, it depends on what we're looking at.

If we're looking at the actual value of n (for example, 30, 100, 10,000), then it's O(log(n)), since log(100) = 2, and 3 operations would occur in your n.foreach.

If we're looking at the number of digits in n (100 has 3 digits), then it's log(n).

CodePudding user response：

For any integer n > 1, n.toString().split("") will have length Math.ceil(Math.log10(n)). Since each of n's digits is less than 10, the sum of n's squared digits (and the updated n value in the while loop after the first iteration) will be no more than (9**2) * Math.ceil(Math.log10(n)) and will have no more than 2 Math.ceil(Math.log10(Math.ceil(Math.log10(n)))) digits. log10(n) is the critical contributor to the number of operations in this function. The time complexity is thus O(log10(n)).