Algorithm Complexity Exercises
Translated by
ScribdTranslationsAlgorithm Complexity Exercises
Translated by
ScribdTranslationsMICAELA BASTIDAS NATIONAL UNIVERSITY
FROM APURÍMAC
PROFESSIONAL SCHOOL OF ENGINEERING COMPUTING AND UNAM BA
SYSTEMS
Algorithm complexity exercises
1. Calculate the theoretical time in the worst case and its order of
complexity of the following algorithm
sum1=0;
for(i=1; i<= n; i++)
for(j=1; j<=n; j++)
sum1 ++;
sum2=0;
for(i=1; i<= n; i++)
for(j=1; j<=i; j++)
sum2++;
2. Calculate the theoretical time in the worst case and its order of
complexity of the following algorithm
public int[] insertionSort(int[] array){
int aux;
for (int i = 1; i < [Link]; i++) {
aux = array[i];
for (int j = i-1; j >= 0 && array[j] > aux; j--) {
array[j+1]=array[j];
array[j]=aux;
}
}
return array;
}
3. Calculate the theoretical time in the worst case and its order of
complexity of the following algorithm
j=0;
i=0:
do{
i=method1();
if(i==-1) break;
j += i;
} while (j<n);
Algorithmics III Ing. Erech Ordoñez Ramos
4. Calculate the theoretical time in the worst case of the following algorithm
For(int i=0;i<n;i++)
For(int j=i;j<n;j++)
2
5. Demonstrate thatT ( n=5∗2+
) n it is in the order of complexity of 2n
3 2
6. Demonstrate thatT ( n=n+9∗n∗log(n)
) it is in the order of complexity
of n3
7. Statement: Which of the following answers are true and which
false? Prove your answers.
a) n2∈O(n3 )
b) 4∗n3−3 i s i n O ( n3)
8. Statement: calculate the recurrence equation and find the cost of
next algorithm:
proc P (n)
{
var i, j: integers
j←1
if n ≤ 1 then finish
if not
for i ← 1 to 7 do P (nDIV2)
for i ← 1 to 4 * n3
}
}
9. Solve and determine the order of complexity of the following
recurrence
{( )
❑
1 n≤4
T ( n )=
T + √n+1n>4
4
10. Solve and determine the complexity order of the following
recurrence
{( )
5 n=1
T ( n )= n
T +5n ≥ 2
3