Question

Consider the following C function:
int fun (int n)
{ int i, j;
for (i = 1; i <= n; i++)
{ for (j = 1; j < n; j + = i)
{ printf{"%d % d", i, j);}}}
Time complexity of fun in terms of $\Theta$ notation is

• A. $\Theta$(n$\sqrt{n}$)
• B. $\Theta$($n^2$ log n)
• C. $\Theta$(n log n)
• D. $\Theta$($n^2$)

Answer 1

The correct option is C $\Theta$(n log n)

First loop will execute 'n' times and the inner loop will execute $\Theta$ (log n) times.
Hence the complexity will be $\Theta$(n log n)