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 (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}
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]
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.
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]
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 )
good