Say we have a directed graph where each vertex vi represents a function fi(n) and there is an edge from vi to vj if and only if fi O(fj) (and i = j,...

Say we have a directed graph where each vertex vi represents a function fi(n) and there is an edge from vi to vj if and only if fi ∈ O(fj) (and i ̸= j, i.e, we don’t put in self-loops). Give a necessary and sufficient condition for this graph to be a DAG. Prove your answer correct. (5 points correct condition, 5 points proof).