Register

ISRO-DEC2017-19

• recategorized by
3,787 views
3 votes
3 votes 
//Consider the program
void function(int n)
{
    int i,j,count=0;
    for(i=n/2;i<=n;i++)
       for(j=1;j<=n;j=j*2)
          count++;
}

The complexity of the program is

  1. $O(\log n)$
  2. $O(n^2)$
  3. $O(n^2 \log n)$
  4. $O(n \log n)$
• recategorized by
User Avatar

2 Answers

Best answer
3 votes
3 votes

Both the loops will run independent of each other.

The outer loop will run for n/2 times.

The inner loop will run for (log n) times.

So, time complexity will be O (n log n).

Option D.

• selected by
User Avatar
Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

9 votes
9 votes
2 answers
1
gatecse asked Dec 17, 2017
3,757 views
ISRO-DEC2017-80
Consider the following $C$ function #include<stdio.h> int main(void) { char c[]="ICRBCSIT17" char *p=c; printf("%s",c+2[p]-6[p]-1); return 0; } The output of the program is $\text{SI}$ $\text{IT}$ $\text{T1}$ $17$
Consider the following $C$ function#include<stdio.h int main(void) { char c[]="ICRBCSIT17" char *p=c; printf("%s",c+2[p]-6[p]-1); return 0; }The output of the program is ...
User Avatar
3 votes
3 votes
2 answers
2
gatecse asked Dec 17, 2017
1,675 views
ISRO-DEC2017-74
Consider the function int func(int num) { int count=0; while(num) { count++; num>>=1; } return(count); } For $func(435)$ the value returned is $9$ $8$ $0$ $10$
Consider the functionint func(int num) { int count=0; while(num) { count++; num>>=1; } return(count); }For $func(435)$ the value returned is$9$$8$$0$$10$
User Avatar
2 votes
2 votes
1 answer
3
gatecse asked Dec 17, 2017
2,146 views
ISRO-DEC2017-73
Consider the function int fun(x: integer) { If x>100 then fun=x-10; else fun=fun(fun(x+11)); } For the input $x=95$, the function will return $89$ $90$ $91$ $92$
Consider the functionint fun(x: integer) { If x>100 then fun=x-10; else fun=fun(fun(x+11)); }For the input $x=95$, the function will return$89$$90$$91$$92$
User Avatar
5 votes
5 votes
1 answer
4
gatecse asked Dec 17, 2017
1,457 views
ISRO-DEC2017-65
Which one of the following are essential features of object-oriented language? A. Abstraction and encapsulation B. Strictly-typed C. Type-safe property coupled with sub-type rule D. Polymorphism in the presence of inheritance $A$ and $B$ only $A,D$ and $B$ only $A$ and $D$ only $A,C$ and $D$ only
Which one of the following are essential features of object-oriented language? A.Abstraction and encapsulation B.Strictly-typed C.Type-safe property coupled with sub-type...
User Avatar
Link Copied!