Hello, I have the following assignment and I do not know how to start.

1. What is the complexity of the following programs. Show all steps of calculations.

a)

Void function(int n)

int i,j,k,count =0

for(i=n/2; i >= n; i++)

for(j = 1; j + n/2 >= n; j++)

for( k = 1; k>= n; k = k* 2)

count++;

b) (3) sum = 0;

for( i = 0; i < n; i++ )

for( j = 0; j < n * n; j++ )

sum++;

2. Find the complexity of the following recursions. Using iterations.

a) T(N) = 2 T(N/2) + N

b) T(N) = 3 T(N/3) + N/2

3. Use Master Theorem to find complexity of the expression.

a) T(N) = 16T(N/4) + N

b) T(N) = 3T(N/2) + N^2 // N^2 is N squared)