CODEWITHSUNDEEP
algorithmtime-complexitybig-o
3xhaust
3xhaust

Reputation: 15

Time complexity of this code confusing me

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?

Upvotes: -1

Views: 78

Answers (3)

user1196549
user1196549

Reputation:

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).

Upvotes: 1

Ulire Ir
Ulire Ir

Reputation: 61

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

it's O(n)

Upvotes: 1

user20657444
user20657444

Reputation:

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

Upvotes: 0

Related Questions