Algorithm

Analysis Lab-1

1) Graph the following expressions (see

Desmos | Graphing Calculator

). For each expression, state the range of values of n for which that expression is the most efficient.

4n

2

log3 n

3n

20n

2

log2 n

n2/3

2) Arrange the following expressions by growth rate from slowest to fastest.

4n2 log3 n n! 3n 20n 2 log2 n n2/3

3) Suppose that a particular algorithm has time complexity T(n) = 3 x 2n, and that executing an implementation of it on a particular machine takes t seconds for n inputs. Now suppose that we are presented with a machine that is 64 times as fast. How many inputs could we process on the new machine in t seconds?

4) Suppose that another algorithm has time complexity T(n) = n2, and that executing an implementation of it on a particular machine takes t seconds for n inputs. Now suppose that we are presented with a machine that is 64 times as fast. How many inputs could we process on the new machine in t seconds?

5) A third algorithm has time complexity T(n) = 8n. Executing an implementation of it on a particular machine takes t seconds for n inputs. Given a new machine that is 64 times as fast, how many inputs could we process in t seconds?

Given functions f(n) and g(n) whose growth rates are expressed as algebraic equations, we might like to determine if one grows faster than the other. The best way to do this is to take the limit of the two functions as n grows towards infinity,

If the limit goes to 1, then f(n) is in (g(n)) because f(n) grows faster. If the

limit goes to zero, then f(n) is in O(g(n)) because g(n) grows faster. If the limit

goes to some constant other than zero, then f(n) = _(g(n)) because both grow at

the same rate.

For each of the following pairs of functions, either f(n) is in O(g(n)), f(n) is in Ω(g(n)), or f(n) = Ɵ(g(n)). For each pair, determine which relationship is correct. Justify your answer, using the method of limits discussed above.

(a) f(n) = log n2; g(n) = log n + 5.

(b) f(n) = ; g(n) = log n2.

(c) f(n) = log2 n; g(n) = log n.

(d) f(n) = log n2; g(n) = (log n)2.

(e) f(n) = 10; g(n) = log 10.

(f) f(n) = 2n; g(n) = 3n.

(g) f(n) = 2n; g(n) = nn.

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

}
}