Question

Consider the following C function.
int fun1 (int n)
{
int i, j, k, p, q = 0;
for (i = 1; i < n; + + i)
{
p = 0;
for (i = n; j > 1; j = j/2)
++p;
for (k = l; k < p; k = k*2)
+ + q:
} return q;
}
Which one of the following most closely approximates the return value of the function fun1?

• A. n (log n)${}^2$
• B. n log (log n)
• C. n log n
• D. $n^3$

Answer 1

The correct option is B n log (log n)

int fun1(int n)
{
int i, j, k, p, q = 20
for (i = 1; i < n; ++ i)
{ P = 0;
for (j = n; j < 1; j = j/2) $\Rightarrow$ log n times for each i $\Rightarrow$ Total = n $\times$ log n ++p;
for (k = 1; k < p; k = k $\times$ 2) $\Rightarrow$ log log n times for each i Total $\Rightarrow$ n log n
++q;
}
return q; $\Rightarrow$ Return value = O(n log log n)
}
Time complexity of above program = O(n log n)
Return value q = O(n log log n)