Register

GATE CSE 2004 | Question: 82

• edited by
20,299 views
66 votes
66 votes

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

  1. $\Omega(n^2)$

  2. $\Omega (n\log n) \text{ and } O(n^2)$

  3. $\Theta(n)$

  4. $o(n)$

• edited by
User Avatar

13 Answers

–5 votes
–5 votes
i think function is called but not defined

means function definition is missing
User Avatar
Page:
Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

31 votes
31 votes
6 answers
1
Kathleen asked Sep 18, 2014
19,450 views
GATE CSE 2004 | Question: 83, ISRO2015-40
The time complexity of the following C function is (assume $n > 0$) int recursive (int n) { if(n == 1) return (1); else return (recursive (n-1) + recursive (n-1)); } $O(n)$ $O(n \log n)$ $O(n^2)$ $O(2^n)$
The time complexity of the following C function is (assume $n 0$)int recursive (int n) { if(n == 1) return (1); else return (recursive (n-1) + recursive (n-1)); }$O(n)$$...
User Avatar
42 votes
42 votes
4 answers
2
Kathleen asked Sep 18, 2014
12,154 views
GATE CSE 2004 | Question: 39
Two matrices $M_1$ and $M_2$ are to be stored in arrays $A$ and $B$ ... column-major order best if both are in row-major order best if both are in column-major order independent of the storage scheme
Two matrices $M_1$ and $M_2$ are to be stored in arrays $A$ and $B$ respectively. Each array can be stored either in row-major or column-major order in contiguous memory ...
User Avatar
47 votes
47 votes
7 answers
3
Kathleen asked Sep 18, 2014
17,630 views
GATE CSE 2004 | Question: 84
The recurrence equation $ T(1) = 1$ $T(n) = 2T(n-1) + n, n \geq 2$ evaluates to $2^{n+1} - n - 2$ $2^n - n$ $2^{n+1} - 2n - 2$ $2^n + n $
The recurrence equation$ T(1) = 1$$T(n) = 2T(n-1) + n, n \geq 2$evaluates to$2^{n+1} - n - 2$$2^n - n$$2^{n+1} - 2n - 2$$2^n + n $
User Avatar
Link Copied!