in Algorithms edited by
179 views
2 votes
2 votes

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))$
in Algorithms edited by
179 views

1 Answer

3 votes
3 votes

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

Answer:

Related questions