MadeEasy Test Series: Algorithms - Time Complexity

Question

please explain answer given c

Comments

where is f(m) in the code?

---

The for loop I think returns the number of 1s from right end or 0 if ends with 0.

The for loop runs n times so TC is of order of n

---

Maybe f(m) is just to confuse?

Answer 1

The question can be titled ambiguity x 100 :p

What I feel the function in else part should be read as f(counter) instead of if (counter).

Lets analyze the code

• The for loop will run n times Θ(n)
• if last elements of array is 0 and rest of the elements are continuously 1, Function f can have maximum complexity of Θ(n-1) only . In that case the function f will run hardly a few times. Hence we can neglect it.
• If array has 0 and 1 frequently present, then f will be called frequently, but counter value will be small. Hence complexity of f will be small. So we ca neglect complexity of f in this case also

In short, we need to consider complexity of for loop only.

Thus answer will be c ) Θ(n)

Comments

"The question can be titled ambiguity x 100" :D I had a good laugh. Thanks :P

Answer 2

As array A[1...n] having n elements. For loop will run n times. It is not depending on If and else condition here.

So, as for loop is running n times time complexity is O(n).

Comments

It is not depending on If and else condition here.

Can you please elaborate it further.