Data structures and algorithms

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.

4n2

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.