- log2n = log3 n < √ n < n1.2 < n3 + log n = n3 – n √ n < 2n < 3n < 32n-1 = 32n < n! < 1.51.5n.
Notes:
- log2n = (log2 3)log3 n, which means that logs with different bases only differ from one another by a constant factor.
- that 32n = 3 * 32n-1 = 9n.
- 1.51.5n is a double exponential, and grows faster than any exponential (even n! or nn). To see this, note that log (1.51.5n) = 1.5n (up to a constant factor), while log n! = n log n. So if log (1.51.5n) grows faster than log n!, then 1.51.5n must grow faster than n!.
- We shall assume that we know how many vertices the graph has. The solution is to do a depth-first or breadth-first search starting at an arbitrary vertex, counting the number of distinct vertices the search finds. It will be equal to the number of vertices of the graph if and only if the graph is connected.
- The proof is by induction of n. If n = 1, then no split can be made, and the sum is 0. Clearly 0 = (1 * 0) / 2.For the induction step, suppose we have n stones. Our induction hypothesis is the following: for every group with fewer than n stones (say s stones), the sum obtained in the way described by the problem will be s(s-1)/2.
Assume that the two piles we create in the initial split contain x stones and n - x stones respectively. By the induction hypothesis, the sum obtained from the splits of the first pile is x(x-1)/2, and the sum obtained from the splits of the second pile is (n-x)(n-x-1)/2. The total is therefore x(x-1)/2 + (n-x)(n-x-1)/2 + x(n-x) which, after the algebra is resolved, becomes n(n-1)/2 as required. This completes the induction step and the proof of the result.