Consider the following C function.int. fun (int n) {

Home » Programming & Data Structure » Programming and data structure miscellaneous » 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 Θ notation is

1. Θ (n √n)
2. Θ (n²)
3. Θ (n log n)
4. Θ (n² log n)

Correct Option: C

In the given program,
First loop will execute 'n' times and the inner loop (j), will execute Θ(n log (n)) times because for (i = 1), j will
run from 1 to n by incrementing by '1' in each step j will run for n times, for (i = 2).
Similarly j will run from 1 to n by incrementing by '2', in each step j will run for (n/2) times and so on.
Then the time complexity

T_n =	n	+	n	+	n	+	n	......log(n - 1)
	1		2		3		(n - 1)

= n		1	+	1	+	1	+	1		- log(n - 1)
		1		2		3		(n - 1)

= nlog(n - 1) - log(n - 1)
= nlog(n - 1)
∴ By neglected negative terms = Θ( n log)
Hence option (c) is correct.