Time complexity of if-else statements in a for loop

Question

Let A[1, …, n] be an array storing a bit (1 or 0) at each location, and f(m) is a function whose time complexity is θ(m). Consider the following program fragment written in a C like language:

Case 1 :-

counter = 0;
for (i = 1; i < = n; i++)
{ 
  if (A[i] == 1) 
     counter++;
  else {
     f(counter); 
     counter = 0;
  }
}

Case 2 :-

counter = 0;
for (i = 1; i < = n; i++)
{ 
  if (A[i] == 1) 
     counter++;
  else {
     counter = 0;
     f(counter); 
  }
}

The complexity of this program fragment is

(A) Ω(n2)

(B) Ω(nlog n) and O(n2)

(C) θ(n)

(D) O(n)

the question is how do i know that when if statement or else statement is used and when the f(m) function is called , How do i approach it? i can consider the cases when only if is executed or only else but what about general case when if statement is executed sometimes and else statement sometimes

Answer 1

We can start by looking at the easy case, case 2. Clearly, each time we go through the loop in case 2, one of either 2 things happens:

1. count is incremented (which takes O(1) [except not really, but we just say it does for computers that operate on fixed-length numbers (that is, 32-bit ints)])
2. count is set to 0 (which takes O(1) [again, debatable]) and f(count) is evaluated (which definitely takes constant time)

we go through the loop n times, each time takes practically O(1) time, bada-bing, bada-boom, it takes O(n) (or O(n * lg(n)) if you're being pedantic and using variable-length integers).

Case 1, on the other hand, requires a little bit of mathematical thinking.

The bit strings that take the shortest amount of time in Case 1 are obviously 11111....11111, 000....000, 000...0111...111, or similar. All of these take θ(n) time to complete, establishing a lower bound for case 1. Now, we need to establish a worst-case scenario.

Without going into the rigor of a proper proof, it's pretty straightforward to assert that the worst-case bit strings look like this:

111....1110

A bit string of the above form with length 100 would have 99 1's, and therefore would need 99 + 99 time units to complete. A string of length n clearly needs 2(n - 1) time units to complete.

This is clearly still linear in n, so case 1, even in the worst case scenario, is θ(n).

Because both case 1 and case 2 are θ(n), the problem is θ(n).

---

If you still need to be convinced that 11.....110 is the worst case bit string, consider this:

A bit string of the form
|--------------n bits------------|
1....101....101....10......1....10
|-L1-| |-L2-| |-L3-|       |-Lm-|
11110
Where L1 - Lm are arbitrary integers will require time 
t = (L1) + (L2) + (L3) + ... + (Lm) + (n - m)
  = sum(L1 to Lm) - m + n

the more "runs" of ones there are, the larger the - m factor is.  If we 
just have one big "run" of ones, we have

t = n - 1 + n - 1 = 2(n - 1)

---

As a matter of principle, I don't answer poorly asked homework questions on stackoverflow.

After talking to coder101 in chat, however, he/she showed me that this is NOT a homework problem, but is instead a problem that was retrieved from an online database here, which is meant to provide "mock tests for geeks". This looks like a challenge that coder101 bestowed upon themselves, and while it could be a better question, I don't think it's that bad.