Therefore,
21. Show that if f (n) = Θ (log 2 n), then f (n) = Θ (log 10 n).
22. Draw a picture of the graph with vertices {υ 1 , υ 2 , υ 3 } and edges {(υ 1 , υ 1 ),
(υ 1 , υ 2 ), (υ 2 , υ 3 ), (υ 2 , υ 1 ), (υ 3 , υ 1 )}. Enumerate all cycles with base υ 1 .
23. Let G = (V, E) be any graph. Prove the following claim: If there is any walk
between υ i ∈ V and υ j ∈ V, then there must be a path of length no larger than
|V| − 1 between these two vertices.
24. Consider graphs in which there is at most one edge between any two
vertices. Show that under this condition a graph with n vertices has at most
n 2 edges.
25. Show that
26. Show that
27. Prove that for all n ≥ 4 the inequality 2 n < n! holds.
28. The Fibonacci sequence is defined recursively by
with f(1) = 1, f (2) = 1. Show that
(a) f (n) = O (2 n ),
(b) f (n) = Ω (1.5 n ).
29. Show that is not a rational number.
21. Show that if f (n) = Θ (log 2 n), then f (n) = Θ (log 10 n).
22. Draw a picture of the graph with vertices {υ 1 , υ 2 , υ 3 } and edges {(υ 1 , υ 1 ),
(υ 1 , υ 2 ), (υ 2 , υ 3 ), (υ 2 , υ 1 ), (υ 3 , υ 1 )}. Enumerate all cycles with base υ 1 .
23. Let G = (V, E) be any graph. Prove the following claim: If there is any walk
between υ i ∈ V and υ j ∈ V, then there must be a path of length no larger than
|V| − 1 between these two vertices.
24. Consider graphs in which there is at most one edge between any two
vertices. Show that under this condition a graph with n vertices has at most
n 2 edges.
25. Show that
26. Show that
27. Prove that for all n ≥ 4 the inequality 2 n < n! holds.
28. The Fibonacci sequence is defined recursively by
with f(1) = 1, f (2) = 1. Show that
(a) f (n) = O (2 n ),
(b) f (n) = Ω (1.5 n ).
29. Show that is not a rational number.