179 views

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”);
}
1. $\theta (n)$
2. $\theta (n^2)$
3. $\theta (n\log n)$
4. $\theta (n^2(\log n))$

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!) = O(nlogn)$

by

1 vote