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