Data structures and algorithms
Algorithm Analysis Lab-2
Exact Analysis Rules
1. We assume an arbitrary time unit.
2. Execution of one of the following operations takes time 1:
a) assignment operation
b) single I/O operations
c) single Boolean operations, numeric comparisons
d) single arithmetic operations
e) function return
f) array index operations, pointer dereferences
3. Running time of a selection statement (if, switch) is the time for the condition evaluation + the maximum of the running times for the individual clauses in the selection.
4. Loop execution time is the sum, over the number of times the loop is executed, of the body time + time for the loop check and update operations, + time for the loop setup. Always assume that the loop executes the maximum number of iterations possible
5. Running time of a function call is 1 for setup + the time for any parameter calculations + the time required for the execution of the function body.
1) Determine a function T(n) to describe the following algorithm using the exact analysis rules provided above. Mark the time used for each line.
Sum = 0;
while ( In.hasNextInt() ) {
Value = In.nextInt();
if ( Value < 0 ) {
Sum = -Sum;
Sum = Sum + Value;
}
else {
Sum = Sum + Value;
}
}
2) Determine a function T(n) to describe the following algorithm using the exact analysis rules provided above.
for (i = 0; i < n-1; i++) {
for (j = 0; j <= i; j++) {
aray[i][j] = 0;
}
}
3) Determine a function T(n) to describe the following algorithm using the exact analysis rules provided above. Mark the time used for each line and include for loop statements.
Sum = 0;
for (k = 1; k <= n; k = 2*k) {
for (j = 1; j <= n; j++) {
Sum++;
}
}