Algo doubt

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

  1. Ω(n2)

  2. Ω(nlogn) and O(n2)

  3. Θ(n)

  4. o(n)

Gaurav Mohla @gauravmohla
15 Oct 2017 08:33 pm
4? I would say the for loop goes for O(n) and that's it. Rest is all constant. f() has constant runtime
shivani @shivani1234
16 Oct 2017 12:03 am

best case when all are 1's then , time complexity is Ω(n)
worst case happens when all are 0's ,then , time complexity is O(n2)
average case happens when it has equal no. of 0's and 1's, then , time complexity is O(n2)
o(n) is false since it means strictly lower , so correct ans is Θ(n)