Asymptotic Notation – Algorithm – Mock Test -1


Question 1
Consider two function

f(n)=n^{1+\frac{1}{\log n}}

g(n)=n \log ( \log n)

Which of the following is/are true?
[MSQ Question]
A
f(n)=O(g(n))
B
g(n)=O(f(n))
C
f(n)=\Theta (g(n))
D
g(n)=\Omega (f(n))
   Algorithm
Question 1 Explanation: 
In this types of complex function, we can not directly compare given functions f(n) and g(n) by putting value of n.

So, we have to use the concept of taking log on both function f(n) and g(n) and then compare both to find the relation in terms of which function is of higher order.

\begin{aligned} \log (f(n))&=\log (n^{1+\frac{1}{\log n}}) \\ &= \left ( 1+\frac{1}{\log n} \right ) \log n\\ &= \log n+1 \end{aligned}

\begin{aligned} \log (g(n))&=\log ( n \log (\log n)) \\ &= \log n + \log ( \log (\log n)) \end{aligned}

Now, comparing both function is easy by just taking differen value of n.
NOTE: Take higher value of n when comparing both function and choose value of n which makes calculation easy.

For example
n=2^{2^{2^{100}}}

(Value of n is selected such that calculation of three times log become easy)

Then, value of
\begin{aligned}\log (f(n))&=\log(2^{2^{2^{100}}})+1\\& =2^{2^{100}}+1\end{aligned}

\begin{aligned}\log (g(n))&=\log (2^{2^{2^{100}}}) + \log ( \log (\log (2^{2^{2^{100}}}))) \\ &=2^{2^{100}}+ \log (\log {2^{2^{100}}})\\ & =2^{2^{100}}+\log( {2^{100}})\\ &=2^{2^{100}}+100\end{aligned}.

Based on above anlysis, we can say that, g(n) is of higher order compared to f(n).

Option A:
f(n)=O(g(n)) is true as said above g(n) is of higher order than f(n)

Option B:
g(n)=O(f(n)) is false.

Option C:
f(n)=\Theta (g(n)) is false as f(n)=\Omega (g(n)) is not true.

Option D:
g(n)=\Omega (f(n)) is true as said above g(n) is higher order than f(n).

(For any confusion, See the basic property of Asymptotic Notation PDF || Video )

Click to Join Our Telegram Group for Latest Update of MOCK TEST
Question 2
int fun(int n) 
{
 int temp = 0;
 if (n < 100000000) 
 {
  for (int i = 0; i < n * n * n; i++) 
  {
  temp++;
  } 
  return temp;
 } 
 if (n % 2 == 0) 
 {
  for (int i = 0; i < n; i++) 
  {
   temp++;
  }
 }
 else 
 {
  for (int i = 0; i < n * n; i++) 
  {
  temp++;
  }
 } 
 return temp;
}
}
Which of the following claims about the overall asymptotic runtime for this function is/are true?
[MSQ Question]
A
\Theta (n)
B
O (n^2)
C
O (n^3)
D
\Omega (1)
   Algorithm
Question 2 Explanation: 
Here,
Even values of n will trigger the best case behavior. (if(n%2) condition becomes true)
Odd values of n will trigger the worse case behavior. (if(n%2) condition becomes false).

Considering the worse case

For asymptotic notation, consider large value of n (n \gt 100000000)
hence, efffect of if (n \lt 100000000) can be ingnored as it is true only for value of (n \lt 100000000)

For (n \gt 100000000) and odd value of n, following code executes 
else {
for (int i = 0; i < n * n; i++) {
temp++;
}
with O(n^2) time complexity.

Therefore, Overall time comlexity of the above code is O(n^2).

Based on obove anlysis,
Option A is false.
Option B is true.
Option C is true
Option D is true.

(For any confusion, See the basic property of Asymptotic Notation PDF || Video )

Click to Join Our Telegram Group for Latest Update of MOCK TEST


Question 3
int fun(int n) 
{
 int temp = 0;
 if (n < 100000000) 
 {
  for (int i = 0; i < n * n * n; i++) 
  {
  temp++;
  } 
  return temp;
 } 
 if (n % 2 == 0) 
 {
  for (int i = 0; i < n; i++) 
  {
   temp++;
  }
 }
 else 
 {
  for (int i = 0; i < n * n; i++) 
  {
  temp++;
  }
 } 
 return temp;
}
}
Which of the following claims about the return value temp using asymptotic notation for this function is/are true?
[MSQ Question]
A
\Theta (n)
B
O (n^2)
C
O (n^3)
D
\Omega (1)
   Algorithm
Question 3 Explanation: 
NOTE: For asymptotic notation, consider large value of n (n \gt 100000000)

hence, efffect of if (n \lt 100000000) can be ingnored as it is true only for value of (n \lt 100000000)

Here,
Even values of n will trigger the best case behavior. (if(n%2) condition becomes true)
Odd values of n will trigger the worse case behavior. (if(n%2) condition becomes false).

Considering the worse case

For (n \gt 100000000) and odd value of n, following code executes 
else {
for (int i = 0; i < n * n; i++) {
temp++;
}


So, temp valaue can be O (n^2).

Based on above anlysis, we can say that.

Option A: is false.
Option B: is true.
Option C: is true.
Option D: is true.
(For any confusion, See the basic property of Asymptotic Notation PDF || Video )

Click to Join Our Telegram Group for Latest Update of MOCK TEST
Question 4
 void fun(int n) 
{
 for (int i = n; i > -n; i--)
 {
  for (int j = 0; j < i; j++) 
  {
   printf("%d",j);
  }
 }
}
Which of the following claims about the overall asymptotic runtime for this function is/are true?
[MSQ Question]
A
\Theta (n^2)
B
O (n^3)
C
\Theta (n)
D
\Omega (n)
   Algorithm
Question 4 Explanation: 


(For any confusion, See the basic property of Asymptotic Notation PDF || Video )

Click to Join Our Telegram Group for Latest Update of MOCK TEST
Question 5
 void fun(int n) 
{
 int sum=0; 
 for (int i = n; i > -n; i--)
 {
  for (int j = 0; j < i; j++) 
  {
   sum++;
  }
 }
 return sum;
}
Which of the following claims about the return value of this function is/are true?
[MSQ Question]
A
\Theta (n^2)
B
O (n^3)
C
\Theta (n)
D
\Omega (n)
   Algorithm
Question 5 Explanation: 
Here, inner for loop executes i times for each iteration of outer loop.

So total number of times sum++ executes is \sum_{i=n}^{i=1}i=\frac{n(n+1)}{2}=O(n^2)

Option A: is true.
Option B: is true.
Option C: is false.
Option D: is true.

(For any confusion, See the basic property of Asymptotic Notation PDF || Video )

Click to Join Our Telegram Group for Latest Update of MOCK TEST


There are 5 questions to complete.

1 thought on “Asymptotic Notation – Algorithm – Mock Test -1”

Leave a Comment