###### Question 9527 – Time-Complexity

February 13, 2024###### Question 9571 – Time-Complexity

February 13, 2024# 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.

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

^{2})Ω(nlogn) and O(n

^{2})θ(n)

o(n)

Subscribe

Login

0 Comments