Exercises on Algorithm Complexity Analysis
Uploaded by
ScribdTranslationsExercises on Algorithm Complexity Analysis
Uploaded by
ScribdTranslationsExercises - Algorithm Complexity Claudio Henríquez Berroeta
I. Algorithm Complexity
1. Calculate the execution time T(n) for the algorithm Cosa(n,A). Clearly identify the time.
that was considered for each instruction.
PROCEDURE Thing(n: integer; A: array [0..n, 0..n] of integer); PROCEDURE Rec (n: integer);
var begin
i, j: integer; if n=1 then
begin A[n, n] := A[n, n] + 1;
i:= 1; else begin
repeat Rec (n-1);
A[i, 0] := 0; Rec (n-1);
for j:= 1 to i do begin end;
A[i, j]:= 0; end;
Rec (i);
end;
i:= i+1;
until i >= n;
end;
2. Calculate the execution time T(n) and order O for the algorithm DivVenc(i,j), considering that the
cost of the function Operations 1 and that the initial input esi=1 and j=n. Clearly identify the
time considered for each instruction.
PROCEDURE DivVenc (i, j: integer) PROCEDURE Combine (i, j: integer)
if (i = j) then for k:= i to j do
Combine (i, j); for q:= i to j do
else begin Operation(i, j, k, q);
m := (i + j) / 2;
a := (j - i) / 4;
DivVenc (i, m);
DivVenc (i+a, m+a);
DivVenc (m+1, j);
Combine (i, j);
end;
3. Calculate the execution time and order of the mystery function, assume the declaration of
variables with zero cost.
int mystery(int n){
int i,j,k,s;
s:=0;
for(i=1; i<n; i++)
for(j=i+1; j<=n; j++)
for(k=1; k<=j; k++)
s=s+2;
return s;
}
Exercises - Algorithm Complexity Claudio Henríquez Berroeta
4. Calculate the execution time T(n) for the algorithm First(n). Clearly identify the
time considered for each instruction.
PROCEDURE First (n: integer); Function Second (x: integer): real;
var var
i: integer; j,k:integer;
now: real; begin
begin k:=0;
if n>0 then begin for i=1 to x do
now:= 0; k:=k+random(100);
for i:= 1 to 2 do First(x divided by 2);
now := now + Second(n); First(x divided by 2);
now Second:=k/x;
end; end;
end;
5. According to the definition of the Ackermann function:
a. Perform the trace for m=2 and n=1. It must include development.
b. Write a recursive function in C (ANSI) or Java ackerman(m,n), which allows obtaining it.
result from two positive integers.
c. Obtain its complexity.
6. Find the recurrence equation and the Order of the following algorithm:
boolean Search (Vector A, int iz, int de, ElementType x)
{ int mitad;
if (iz > de)
return (False);
else {
middle = (left + right) / 2;
if (A[middle] == x)
return(True);
else
if (A[mid] > x)
return (Search(A, left, mid-1, x));
else
return (Search(A, mid + 1, de, x));
}
}
Exercises - Algorithm Complexity Claudio Henríquez Berroeta
7. Suppose that the input of a certain problem P of size n to solve it is found in the
literature the following alternatives:
AlternativeA: time algorithm O n n log n 2n
AlternativeB: transform it into another problem for which a time algorithm is known.
O n3 n2n the transformation takes time O nlog n2
AlternativeC: model it in a binary tree of n levels and execute for each node of the tree a
time algorithm O n2 Which alternative do you choose?
8. Find the recurrence equation and the Order of the following algorithm:
boolean Search (Vector A, int from, int to, ElementType x)
{ int mitad;
if (iz > de)
return (False);
else {
tercio = (iz + de) / 3;
if (A[third] == x)
return(True);
else
if (A[third] > x)
return (Search(A, left, third-1, x));
if (A[third] < x && A[third*2] > x)
return (Search(A, third+1, 2*third-1, x));
else
return (Search(A, 2*third+1, of, x));
}
}
9. Calculate the execution time T(k) and Order for the algorithm Div23(k). Clearly identify.
the time he considered for each instruction. Assume that the operation EsPrimo(x) requires a
constant time.
PROCEDURE Div23 (k: integer);
begin
if k <=1 then
Does recursion end?
else
if EsPrimo(2k-1) then
Div23 (k/2)
else begin
Div23 (k div3);
Div23 (k div3+1);
end;
end;
Exercises - Algorithm Complexity Claudio Henríquez Berroeta
10. Calculate the execution time and order O of the following code.
Sum = 0;
i = 0;
while (i < n) {
j = 0;
while (j < n) {
Sum = Sum + Matrix[i][j];
j ++;
}
i++;
}
11. For a problem of large input size, there are 3 alternatives to solve it:
AlternativeA: time algorithmO ( n3+n⋅log(n3 ) )
Alternative B: transform it into another problem for which a time algorithm is known.
n+ n
O( 2 √ ) the transformation takes time ( n⋅logn ) .
AlternativeC: model it in a binary tree with vertices and execute for each vertex of the tree a
time algorithm ( ( )3 √ ) .
logn +n n
What alternative do you consider the most efficient?
12. Solve the recurrent equation: t(n) - 2t(n-1) = n + 2n, with n > 0, and t(0) = 0.
13. Suppose that the input of a certain problem P of size n to solve it is found in
the literature the following alternatives:
AlternativeA: time algorithm
Alternative B: transform it into another problem for which a time algorithm is known. ,
the transformation takes time
AlternativeC: model it in a binary tree with n vertices and execute for each level of the tree a
time algorithm
Which alternative do you choose?
Exercises - Algorithm Complexity Claudio Henríquez Berroeta
14. Calculate the execution time of the procedure Algorithm (1 point)
procedure Algorithm (x: array [1..MAX, 1..MAX] of real; n: integer)
var
i, j: integer;
a, b, c: array [1..MAX, 1..MAX] of real;
begin
if n > 1 then begin
for i:= 1 to n divided by 2 do
for j:= 1 to n/2 do begin
a[i, j] := x[i, j];
b[i, j] := x[i, j + n divided by 2];
c[i, j] := x[i + n divided by 2, j];
end;
Algorithm (a, n divided by 2);
Algorithm (b, n div 2);
Algorithm (c, n div 2);
end;
end;