Question 9570 – Time-Complexity

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

Correct Answer: C

Question 21 Explanation:

If the string contains all zero’s then it takes O(n) time, because f(n) can call n times.
If the string contains all one’s then it takes O(n) time, because counter++ can execute n times.
If it contains half 0’s and half 1’s then also it takes O(n) time.

Ω(n²)

Ω(nlogn) and O(n²)

θ(n)

o(n)

0 0 votes

Article Rating

0 Comments

Inline Feedbacks

View all comments