Skip to content
GATETECH
Official PYQ · 2004Q82Asymptotic Worst Case Time and Space ComplexityMCQ1 mark

GATE CS 2004 Q82 — Asymptotic Worst Case Time and Space Complexity

Explain with AI

Let A[1,…,n]A[1,\ldots,n] be an array storing a bit (11 or 00) at each location, and f(m)f(m) is a function whose time complexity is Θ(m)\Theta(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

Choose one option
View worked solution

Answer: C

To find the total time complexity of the program fragment, let us analyze the work done in each iteration of the loop:

  1. Loop Overhead: The loop runs exactly nn times, contributing Θ(n)\Theta(n) time for index increments and conditional checks.
  2. Inside the Loop:
    • When a[i]==1a[i] == 1, we increment counter, taking Θ(1)\Theta(1) time.
    • When a[i]==0a[i] == 0, we call f(counter)f(\text{counter}) and reset counter to 00. Since f(m)=Θ(m)f(m) = \Theta(m), this call takes time proportional to the number of consecutive 11s seen since the last 00.

Let the lengths of consecutive blocks of 11s in the array be m1,m2,…,mkm_1, m_2, \ldots, m_k. Since the total number of elements in the array is nn, the sum of the lengths of these blocks cannot exceed nn:

∑j=1kmj≤n\sum_{j=1}^{k} m_j \le n

The total time spent executing the function ff across all iterations is:

∑j=1kΘ(mj)=Θ(∑j=1kmj)=O(n)\sum_{j=1}^{k} \Theta(m_j) = \Theta\left(\sum_{j=1}^{k} m_j\right) = O(n)

Combining the loop overhead and the function calls, the overall time complexity is Θ(n)+O(n)=Θ(n)\Theta(n) + O(n) = \Theta(n).

Free practice · Your answers on this page are not saved.

Published
Report a correction
Keep exploringMore Asymptotic Worst Case Time and Space Complexity questions