# Computational complexity of a few algorithms

• June 7th, 2013, 04:23 AM
Quentin026
Computational complexity of a few algorithms
Hi there,

I'm reading a book about data structures and algorithms and I've done 3 exercises on finding computational complexity of the given algorithms. Computational complexity in this case means taking into account the overall number of assignments in the code. I'd like you to check my calculations and determine whether I've chosen a proper big-O notation for the function (I have some difficulties with arranging sigma notation). I wasn't sure about class O for the first exercise.

Quote:

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++;```

http://img211.imageshack.us/img211/5...enshotfhmx.png

What do you think about my solutions?