CODEWITHSUNDEEP
algorithmtime-complexity
user6817758
user6817758

Reputation: 13

Questions on analyzing time complexity

Hi I have some doubts about my analysis on the following two code fragment:

1)

    for (i = 1; i <= 1.5n; i++)
        for (j = n; j >= 2; j--)
            cout << i, j;

The outer loop will be executed 1.5n times, and the inner loop will be executed n-2 times. Therefore, the complexity is O(1.5n*(n-2) = O(n^2)?

2) 

    j = 1;
    while (j < n/2) {
        i = 1;
        while (i < j) {
            cout << j << i;
            i++;
        }
        j++;
    }

The outer while loop will be executed n/2 times, and the inner while loop will be executed 1+2+...+n/2 times. Therefore, the complexity is also O(n^2)?

I was not so sure about my analysis on second problem.

Thank you so much for the help!

Upvotes: 1

Views: 631

Answers (1)

md5
md5

Reputation: 23699

You're right. The right solution is to count.

Note that:

j = 0;
while (j < n/2) {
    j++;
}

has a O(n)complexity, whereas:

j = 1;
while (j < n) {
    j *= 2;
}

has a O(log n) complexity.

Upvotes: 1

Related Questions