1. Find the complexity of the function used to find the kth smallest integer in an unordered array of integers:

Code:

int selectkth(int a[], int k, int n)
{
int i, j, mini, tmp;
for(i = 0 ; i < k ; i++)
{
mini = i;
for(j = i+1 ; j < n ; j++)
if(a[j]<a[mini])
mini = j;
tmp = a[i];
a[i] = a[mini];
a[mini] = tmp;
}
return a[k-1];
}

2. Determine the complexity of the following implementations of the algorithms for adding, multiplying, and transporting n X n matrices:

Code:

for(i = 0 ; i < n ; i++)
for(j = 0 ; j < n ; j++)
a[i][j] = b[i][j] + c[i][j];
for(i = 0 ; i < n ; i++)
for(j = 0 ; j < n ; j++)
for(k = a[i][j] = 0 ; k < n ; k++)
a[i][j] += b[i][k] * c[k][j];
for(i = 0 ; i < n - 1 ; i++)
for(j = i+1 ; j < n ; j++)
{
tmp = a[i][j];
a[i][j] = a[j][i];
a[j][i] = tmp;
}

3. Find the computational complexity for the following four loops:

Code:

for(cnt1 = 0, i = 1 ; i <= n ; i++)
for(j = 1 ; j <= n ; j++)
cnt1++;
for(cnt2 = 0, i = 1 ; i <= n ; i++)
for(j = 1 ; j <= i ; j++)
cnt2++;
for(cnt3 = 0, i = 1 ; i <= n ; i *= 2)
for(j = 1 ; j <= n ; j++)
cnt3++;
for(cnt4 = 0, i = 1 ; i <= n ; i *= 2)
for(j = 1 ; j <= i ; j++)
cnt4++;