Big-O small clarification

Question

Is O(log(log(n))) actually just O(log(n)) when it comes to time complexity?
Do you agree that this function g() has a time complexity of O(log(log(n)))?

int f(int n) {
    if (n <= 1)
        return 0;
    return f(n/2) + 1;
}

int g(int n) {
    int m = f(f(n));
    int i;
    int x = 0;
    for (i = 0; i < m; i++) {
        x += i * i;
    }
    return m;
}

Answer 1

function f(n) computes the logarithm in base 2 of n by repeatedly dividing by 2. It iterates log₂(n) times.

Calling it on its own result will indeed return log₂(log₂(n)) for an additional log₂(log₂(n)) iterations. So far the complexity is O(log(N)) + O(log(log(N)). The first term dominates the second, overall complexity is O(log(N)).

The final loop iterates log₂(log₂(n)) times, time complexity of this last phase is O(log(log(N)), negligible in front of the initial phase.

Note that since x is not used before the end of function g, computing it is not needed and the compiler may well optimize this loop to nothing.

Overall time complexity comes out as O(log(N)), which is not the same as O(log(log(N)).

Answer 2

Looks like it is log(n) + log(log n) + log(log n).

In order: the first recursion of f(), plus the second recursion of f(), and the for loop, so the final complexity is O(log n), because lower order terms are ignored.