Not O(N²), but O(log N)

When I saw this algorithm below at first, I thought the time of complexity was O(N²). However, it is O(log N). I’ll explain it.

let fibonacci = function(n){
    let first = 0
    let second = 1
    let sum = 0;
    for(let i = 0; i < n; i++){
        sum = twist(first) + twist(second);
        first = second;
        second = sum;
    }
    return first;
}

let twist = function(n){
    let ans = 0;
    while(true){
        ans *= 10;
        let digit = Math.round((n / 10 - Math.floor(n / 10)) * 100)  /100;
        ans += digit;
        n = Math.floor(n / 10);
        if(n < 1){
            return ans * 10;
        }
    }
}


console.log(fibonacci(10)) //=> 514
console.log(fibonacci(13)) //=>4139
console.log(fibonacci(3)) //=> 2

What the algorithm wants to do is calculating fibonacci. But, the numbers have to be twisted. There is a for statement in the fibonacci function and a while statement in the twist function, so I thought it would be O(N²). But, the twist function’s complexity grows logarithmically because the answer is multiplied by 10 (ex. log1000 = 3, log10000 = 4), which means it is a natural logarithm. Therefore, the time of complexity becomes O(N logN).

Feel free to reach out to me on LinkedIn, which you can find below. Looking forward to connecting!

https://www.linkedin.com/in/tomoharu-tsutsumi-56051a126/