Question 1 |

Consider functions Function 1 and Function 2 expressed in pseudocode as
follows:

Let f_1(n) and f_2(n) denote the number of times the statement "x = x + 1" is executed in Function 1 and Function 2, respectively.

Which of the following statements is/are TRUE?

Let f_1(n) and f_2(n) denote the number of times the statement "x = x + 1" is executed in Function 1 and Function 2, respectively.

Which of the following statements is/are TRUE?

f_1(n)\in \Theta (f_2(n)) | |

f_1(n)\in o (f_2(n)) | |

f_1(n)\in \omega (f_2(n)) | |

f_1(n)\in O (n) |

Question 1 Explanation:

Question 2 |

Let f and g be functions of natural numbers given by f(n)=n and g(n)=n^2.

Which of the following statements is/are TRUE?

Which of the following statements is/are TRUE?

f \in O(g) | |

f \in \Omega (g) | |

f \in o(g) | |

f \in \Theta (g) |

Question 2 Explanation:

Question 3 |

Which one of the following statements is TRUE for all positive functions f(n)?

f(n^2)=\theta (f(n)^2), where f(n) is a polynomial | |

f(n^2)=o (f(n)^2) | |

f(n^2)=O (f(n)^2), where f(n) is an exponential function | |

f(n^2)=\Omega (f(n)^2) |

Question 3 Explanation:

Question 4 |

Consider the following three functions.

f_1=10^n\; f_2=n^{\log n}\;f_3=n^{\sqrt {n}}

Which one of the following options arranges the functions in the increasing order of asymptotic growth rate?

f_1=10^n\; f_2=n^{\log n}\;f_3=n^{\sqrt {n}}

Which one of the following options arranges the functions in the increasing order of asymptotic growth rate?

f_3, f_2, f_1 | |

f_2, f_1, f_3 | |

f_1, f_2, f_3 | |

f_2, f_3, f_1 |

Question 4 Explanation:

Question 5 |

What is the complexity of the following code?

```
sum=0;
for(i=1;i<=n;i*=2)
for(j=1;j<=n;j++)
sum++;
```

Which of the following is not a valid string?O\left(n^{2}\right) | |

O(n \log n) | |

O(n) | |

O(n \log n \log n) |

Question 5 Explanation:

NOTE: Question is excluded from the evaluation due to ambiguity.

Click here for detail solution by gateoverflow

Click here for detail solution by gateoverflow

There are 5 questions to complete.

Please correct the right options for Q41:

Except a all are true.

Please Update the Q.22’s Option A. Correct answer is log (n)

Question no. 27 have typing mistake

i/2 is wrong

It’s is i/=2

Question Updated.

Please update Q.40

Updated the Question with Option D as correct Answer.

question no-30 please update question to more specific in the last line, it asks for space complexity