CODEWITHSUNDEEP
cperformancetime-complexity
user15246957
user15246957

Reputation:

What effect does this if statement have on the time complexity of these nested loops?

I have here 2 programs that desperately need an efficiency evaluation using the big o notation. For the first one, I'm unsure of the effect of the if statement. This one has a nested loop and they usually have efficiency O(n^2), but I can't be sure. The other one also has the nested loop but with a break; command.

/* modifies a so that all the even numbers appear before
all of the odd numbers. there are multiple possible results
-the order of the even numbers does not matter
-the order of the odd numbers does not matter
*/

void even_first(int a[], int len) {
  int temp = 0;
  for (int i = 0; i < len; ++i) {
    if (a[i] % 2 == 0) {
      temp = a[i];
      for (int j = i; j > 0; --j) {
        a[j] = a[j - 1];
      }
      a[0] = temp;
    }
  }
}
////////////////////////////////////////////////////////////////////
/*  finds the single integer in the inclusive range 1...[len + 1] that does 
not appear in a. Because the elements of a are unique and all in the range
       1...(len + 1), there must be a single integer in that range
that is "missing" from a */
int missing(int a[], int len) { 
  for (int j = 1; j <= len + 1; ++j) {
    bool found = false;
    for (int i = 0; i < len; ++i) {
      if (a[i] == j) {
        found = true;
        break;
      }
    }
    if (!found) {
      return j;
    }
  }
  return -1;
}

Upvotes: 0

Views: 187

Answers (2)

Brandon Kellner
Brandon Kellner

Reputation: 31

The effect of the if statement in the first function is that the second n in n^2 only applies for even numbers. The effect of the shorter loop is that it sort of halves the second n. If you look at the worst case, all evens, you get n * (n + 1) / 2, due to that shorter loop, which comes to O(n^2). The average case is still going to be O(n^2), though with close to a 1/4 factor.

Edit: After reading some comments I think I should add the best, worst and average case scenarios:

Best case, no evens, O(n)

Worst case, all evens, O(n * (n+1) / 2) = O(n^2)

Average case, half evens O(n * (n+1) / 4) (average result for half the evens works out to half the visits of the worst case) = O(n^2)

The break in the second function cuts the second n in n^2 to about half, so again, still O(n^2).

If you're trying to do better than O(n^2), I'm pretty sure you can solve both problems with O(n) if you just make an additional array, but you only asked what the effect of the if statement is and what the big O notation was.

Upvotes: 1

Ryan M
Ryan M

Reputation: 20147

The first one has a worst-case time complexity of O(n2) (all even numbers, or at least a number of even numbers that scales with respect to n, such as random integers). The effect of the if statement is that it improves the best-case time complexity (all odd numbers, so the if statement is always false and the inner loop never runs), which is O(n). The inner loop itself is O(n) because the number of iterations still scales with n.

The second one is O(n2) in the worst case, because it scales with the length of the array and the missing number itself. If the missing element were always 1, it would be O(n), because the outer loop would only run once. Assuming the missing element is random, it's O(n2), because both loops would then scale with length.

Upvotes: 2

Related Questions