- Rank the following functions by order of growth. That is, order them so that f1 ∈ O(f2), f2 ∈ O(f3), etc. Make sure to indicate whether or not fi ∈ Θ(fi+1). For instance you could use the notation n < n^2 = 2n^2 < n^4…
n3 – n √ n
n! log2n 2n 32n log3n n1.2 32n-1 1.51.5n √ n
3n n3 + log n - An undirected graph is connected if for every two nodes N1 and N2, there is a path from N1 to N2 in the graph. Describe a simple algorithm to determine if a given graph is connected. What is the running time of your algorithm?
- Suppose you begin with a pile of n stones, and split this pile into n piles of one stone each by successively splitting a pile of stones into two smaller piles. Each time you split a pile you multiply the number of stones in each of the two smaller piles you form, so that if these piles have r and s stones in them, respectively, you compute rs. Show that no matter how you split the pile, the sum of the products computed at each step equals n(n-1)/2. Here is an example that shows how the computation proceeds:
The sum is 21+2+12+1+3+2+2+1+1 = 45, which is indeed 10 * 9 / 2.