Time complexity of this code confusing me-CodePudding

I'm struggling to understand the concepts of calculating time complexity. I have this code in C, why does the time complexity is O(n) and not O(n log n)? The first loop is running for maximum of 3 iteration, the outer for loop is in logarithmic complexity and each iteration of it doing linear time.

int f2 (int n)
{
    int j, k, cnt=0;
    do 
    {
          n;
    } while (n%3);

    for (j=n; j>0; j/=3)
    {
        k=j;
        while (k>0)
        {
            cnt  ;
            k-=3;
        }
    }

    return cnt;
}

Why do we neglecting the log time?

CodePudding user response：

The time complexity of you program is O(n). Because the total number of calculations is : log(n)/log(3) 2 * (n/3 n/9 n/27 ... < log(n) n/2 < 2*n

CodePudding user response：

T = (n n/3 n/9 ... 1)
3*T - T = 3*n-1
T = 1.5*n-0.5

it's O(n)

CodePudding user response：

It is a common beginner's mistake to reason as follows:

the outer loop follows a decreasing geometric progression, so it iteratess O(log n) times.
the inner loop follows an arithmetic progression, so its complexity is O(n).
hence the global complexity is O(n n n ...)=O(n log n).

The mistake is due to the lack of rigor in the notation. The correct approach is

the outer loop follows a decreasing geometric progression, so it iterates O(log n) time.
the inner loop follows an arithmetic progression, so its complexity is O(j) (not O(n) !), where j decreases geometrically.
hence the global complexity is O(n n/3 n/9 ...)=O(n).