Question 9527 – Time-Complexity
February 13, 2024Question 9571 – Time-Complexity
February 13, 2024Question 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.
Ω(n2)
Ω(nlogn) and O(n2)
θ(n)
o(n)
Subscribe
Login
0 Comments