-
June 7th, 2013, 04:23 AM
#1
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.
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++;
What do you think about my solutions?
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|