NIELIT 2022 April Scientist B | Section B | Question: 44

Question

What is the time complexity of the following function?

void myfun()
{
    int a,b;

    for(a=1; a<=n; a++)

        for(b=1; b<=log(a); b++)

            printf(“My Function”);
}

• A. $\theta (n)$
• B. $\theta (n^2)$
• C. $\theta (n\log n)$
• D. $\theta (n^2(\log n))$

Answer 1

Answer: C

When

$a$ = 1, $b$ will run $log(1)$ times,

$a$ = 2, $b$ will run $log(2)$ times,

$a$ = 3, $b$ will run $log(3)$ times,

$...$

$a$ = $n$, $b$ will run $log(n)$ times.

Total time taken = $log(1) + log(2) + log(3) + … + log(n)$

= $log(1*2*3*...*n)$ $=$ $log(n!)$

And when $n$ is large according to Stirling's approximation

$log(n!) = \Theta(nlogn)$

Comments

according to Stirling's approximation

i think it  should be

log(n!) =$\Theta$(nlogn)

kindly explain .