# 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:
 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.