Show the steps of deriving your answers. Points will be deducted for answers without adequate steps discussed. Submit your homework via Blackboard as one PDF or Word document.
(25) [Asymptotic upper bound] Show that n1000000 = O(1.000001n) based on the formal definition of big-O (see below). It suffices to present the values of c and n0 and explain how you obtained them. A complete proof (i.e., that it holds for all n n0) is not required.
Definition. We say T(n) = O(f(n)) if there exist constants c 0 and n0 0 such that T(n) c f(n) holds for all n n0.
(25) [Adjacency matrix and adjacency list] Show an adjacency matrix representation and an adjacency list representation of the directed graph shown below. A node is not adjacent to itself unless there is a self-loop. In addition, show the pseudocode of algorithm Find_all_edges that outputs all edges in the graph, and show its big-O run-time complexity – make sure to show the steps of deriving the run-time complexity; no point will be given to an answer without the steps.
