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?

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

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

Which of the following is/are true?

[MSQ Question][MSQ Question]

f(n)=O(g(n)) | |

g(n)=O(f(n)) | |

f(n)=\Theta (g(n)) | |

g(n)=\Omega (f(n)) |

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

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]

\Theta (n) | |

O (n^2) | |

O (n^3) | |

\Omega (1) |

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

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

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]

\Theta (n) | |

O (n^2) | |

O (n^3) | |

\Omega (1) |

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

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

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]

\Theta (n^2) | |

O (n^3) | |

\Theta (n) | |

\Omega (n) |

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]

[MSQ Question]

\Theta (n^2) | |

O (n^3) | |

\Theta (n) | |

\Omega (n) |

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

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.