Time complexity for code

#1

please explain how to find time complexity for the given code https://ide.codingblocks.com/s/159378

#3

First of all, your program will crash because if(j % i == 0), both i and j are 0
changing your code a bit

void function(int n)
{
int count = 0;
for (int i=1; i<n; i++) // runs O(n) times
for (int j=i; j< ii; j++)
if (j%i == 0) // runs O(i) times
{
for (int k=0; k<j; k++) // runs j times, whenever j is factor of i
//that is when j = i, j = 2i … j = i i
printf("*");
}
}

take an example when i = 5

This implies total complexity is

for (int j=5; j< 25; j++)
if (j%i == 0) // runs O(i) times
{
// runs j times when j = 5, 10, 15, 20
for (int k=0; k<j; k++) {
printf(""); // runs j times when j = 5(1 + 2 + 3+ 4)
// so the print statement runs approximately ii*(i*(i-1)/2) times
// which is almost i^4 times
}
}
this implies total complexity is O(n^4)

1 Like
Time complexity explanation of following
Doubt in time complexity of the following questions
#4

but time complexity is given as o(n^5)

#5

Hello @Faizan-Ali-1395131367301898

First of all, your program will NOT crash when both i and j are 0 because 0 is NOT less than 0.

The complexity
Line 6 will run for N times
Line 7 will run for 1 + 4 + 9 + 16 + … + N^2 times is approx. N^3 times
Line 8 will also run for N^3 times

Line 10 and 11 will run for
(2) times, when i = 2
(3 + 6) times, when i = 3
(4 + 8 + 12) times, when i = 4
(N + 2N + 3N + … + N*(N-1)) times, when i = N

Total = (2) + (3 + 6) + (4 + 8 + 12) + … + (N + 2N + 3N + … + N^(N-1)) times
which is
2(1) + 3(1 + 2) + 4(1 + 2 + 3) + … + N(1 + 2 + … + (N-1))
which is
Summation of (kk(k-1))/2 from k = 2 to k = N
Which when you solve would be something approx N^4

Total complexity will be N + N^3 + N^3 + N^4 i.e., approx N^4

So @mahimahans111 is correct when she says that the complexity would be N^4.

1 Like