CODEWITHSUNDEEP
time-complexity
vesii
vesii

Reputation: 3128

Calculating the time complexity of a specific code in C

Consider the following code in C:

int i = 1;
while(i < n)
{
    if((n – i) % 2)
        i *= 3;
    else
        i *= 2;
}

It's part of a greater code. I'm trying to calculate the time complexity of this code. How should I approach it mathematically? I know how to calculate a linear loop but every time I have to face with a non-linear loop (jumps in the code), I get into trouble.

Upvotes: 1

Views: 1361

Answers (2)

Rob
Rob

Reputation: 1437

In the worst case, it could be log3(n), and in the best case it could be log2(n).

The change in base is just going to be a constant, though. So it's O(lg n), because the constant doesn't matter, and we know that it's in between those two cases.

Upvotes: 1

Maras
Maras

Reputation: 982

Well, if you're looking for time complexity, you can just simulate the algorithm for different values.

In your case: Let's say that n is odd. Then in the first iteration i will be doubled. However, next time (n - i) will be odd, and no matter what you multiply i by, it will never change (i will always be even, so (n - i) will be odd). So every next iteration i will be multiplied by 3. You could say, that in this case your algorithm has O(log3 n) time complexity.

What if n is even? Then in the first interation i will triple. We can easily see, that to (n - i) be even, i has to be even. And it will never get even, because you'll never multiply it by 2. Time complexity is also O(log3 n)

No matter what, your time complexity is O(log3n) in this algorithm. If there are multiple possible time complexities depending on the input, you have to precise what time complexity you actually want to count. Usually that's a worst-case time complexity, so you take the worst of possible complexities you got.

EDIT: Few clarifications: 1) Why do I check if n is even or odd? In your algorithm, the thing that changes the way your algorithm works is the following code: "if((n - i) % 2)" It checks for (n - i) being even or odd. You can't take a different value for i, because it is set to 1 at the beginning. So the only variable I can check is n. I do not care what number n actually is, I only need to know what the result of ((n - i) % 2) will be, so I need to know if n is divisible by 2 or not.

2) If i is being multiplied by 3 every time, why is the complexity O(log3n)? Each time your loop activates, i is being multiplied by 3. So after 100 steps, i will be multiplied by 3^100. Your loop ends when i is bigger or equal to n, and that will happen when 1 * 3^x >= n. 3^x >= n x >= log3(n).

Upvotes: 1

Related Questions