Algorithm Time Complexity Analysis (for loop with inner while loop)

Question

Here's the code I've implemented in a nutshell. The for loop should have a complexity of O(n). I just can't figure out the time complexity of the inner while loop.

int x,n; // Inputted by the user.
for (int i=0; i<n; i++)
{
 int done=0;
 if (Condition)
 {
 while (done < x)
 {
 done++; // Based on a lot of operations
 }
 }
}

I can post the whole code if you want. Thanks in advance :)

• Rerito: The overall inner loop complexity is O(x). But since you do not reset done to 0 the x times that the "inner operations" are run get done all over the outer loop. In the end, these operations are only executed x times.
• Rerito: Then, it gets run each time Condition is triggered, not just the first time. The inner loop complexity stays O(x) (taking the number of times your operations are run as a metrics)
• user3490561: @Rerito Would the overall complexity be O(xn) in this case?
• Rerito: The inner loop complexity is O(x). Once combined with the outer loop, you get a worst-case complexity of O(xn).
• piotrekg2: Time complexity is at most O(nx). Since we dont know what 'Condition' is we cant tell more accurately.

Answer 1

Here, the complexity is measured by studying the number of times the program will run the operations of the inner loop.

Each time Condition is triggered, the inner loop runs x times. Thus the inner loop complexity is O(x).

This loop can run at most n times. This provides you an overall worst-case complexity of O(x.n).

Having additional knowledge about Condition can get you a more precise analysis. You may be able to compute average complexity for example.

As an example : let Condition be !(i & (i-1)). This is true if and only if i is either 0 or a power of 2. In this case, your loop would get run exactly E(ln2(n)) + 2 times (E(.) being the integer part function). In the end, the overall complexity knowing this becomes O(x.ln(n))