##### Complexity Analysis of Iterative Programs
Content covered:

Find the complexity of the following Interative functions:
1.

Check ()
{
int i, n;
for (i=1; i<=n ; i++)
{
printf("Techtud");
}

In the above code, you can analyze that print statement will execute 'n' times because of 'for' loop. So We can say that the time complexity of above code will be O(n).
2.

Check ()
{
int i,j n;
for (i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
printf("Techtud");
}
}

In the above function, For each value of 'i' , the inner for loop will execute from "j=1 to n" .
So for,
i=1, inner loop will execute n times, Hence 'printf' statement will execute 'n' times.
i=2,  inner loop will execute n times, Hnece 'printf' statement will execute 'n' times.
So on, for i=n, printf statement will execute 'n' times.
In total, 'printf' statement will execute a total of  n+n+n+n......................n times = n^2
So complexity of above code will be O(n^2).
3.

​
Check ()
{
int i, n;
for (i=1; i<=n ; i++)
{
for (j=1; j<=i^2 ; j++)
printf("Techtud");
}
}

Here in above function, inner loop is depending on outer loop because of j<=i^2 .
So here,
for i=1, 'printf' will execute 1 time.
for i=2, 'printf' will execute 4 times.
for i=3, 'printf' will execute 9 times.
So on, for i=n, printf will execute n^2 times.
In total, 1+4+9+..................+n^2 = n(n+1)(2n+1)/6.
So complexity of this function will be O(n^3).

4.

​
Check ()
{
int i,j,k n;
for (i=1; i<=n ; i++)
{
for (j=1; j<=i^2 ; j++)
{
for (k=1; k<=n\2 ;k++)
printf("Techtud");
}
}
}

In the above code,
for i=1, first inner loop will execute 1 time and hence innermost loop will execute n/2 times.
for i=2, first inner loop will execute 4 times and hence innermost loop will execute 4*n/2 times.
Similarly for i=3, first inner loop will execute 9 times and hence innermost loop will execute 9*n/2 times.
So on, for i=n, first inner loop will execute n^2 times and hence innermost loop will execute (n^2)*n/2.
In total, n/2 + 4*n/2 + 9*n/2 + ........................ + (n^2) *n/2 = (n/2)(n(n+1)(2n+1)/6)
So complexity will be O(n^4).