(a) What is the largest problem you can solve in an hour if your algorithm takes 3n operations on problems of size n?
(b) What if your algorithm takes 10n2 operations?
(c) ...1000 n lg n operations?
(a) Say you wanted to analyze the genome using the computer of exercise 1 running a naive string matching algorithm known to take n2 operations on inputs of length n. Comment on the feasibility of this.
(b) Suppose that by using a more appropriate data structure, your algorithm could perform the same task using only n lg n operations on inputs of length n. What then?
(a) (n choose k) = Theta(nk) for fixed constant k
(b) lg (n!) = Theta(n lg n) (Hint: use Stirling's formula)
(c) loga n = Theta(logb n) for any positive constants a, b.
n, sqrt n, lg n, lg(lg n), (lg n)2, n2/lg n, 100sqrt n, 2n, n2.