Let A[1, ..., n] be an array storing a bit (1 or 0) at each location, and f(m) is a function whose time…

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:

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

The complexity of this program fragment is

Accepted Answer

Correct answer: C — Answer: θ(n) Reason: Count the work done by the loop and by all calls to f. The for-loop inspects each element A[i] exactly once, which costs Θ(n) overall. Each time a zero is encountered the code calls f(counter) and resets counter. f(counter) costs Θ(counter). All ones in the array are partitioned into groups counted by these counter values (some trailing ones may not trigger a call), so the sum of all counter values over all calls to f is at most the total number of ones ≤ n. Therefore the total cost of all f calls is Θ(n). Combining the scan cost Θ(n) and the f-call cost Θ(n) gives total runtime Θ(n).

Answer

A. Ω(n2)

Answer

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

Answer

C. θ(n)

Answer

D. O(n)

Let A[1, ..., n] be an array storing a bit (1 or 0) at each location, and f(m)…