Vtyjkyuk

Imagine a two-layered course graph, which upper level presents an acyclic directed graph with n nodes, while the lower level presents an acyclic directed graph with m nodes. Each node in the upper level is connected to a few nodes in the lower level (let's say each node in the upper level covers a few nodes in the lower level). So n is less than m (each node in upper level at least covers 2 nodes in lower level).

My questions are:

1- What are the time and space complexities using the depth-first search algorithm to find all sequences from a certain node in the upper level and in the lower level? and how these time and space complexity of two levels can be compared (how they are related)?

My answer about time and score complexities, which I am suspicious about, are as follow:

• Upper level:time complexity:o(n), space complexity: o(n+e) (e: number
  of edges).


• Lower level:time complexity:o(m), space complexity: o(m+e)
  (e: number of edges).

But I can not find the relation among these two.

2- If we want to find all possible sequences from a single node in the lower level of the graph, if an additional node will be added to this graph, how the number of sequences increases (for the worst case scenario)?

Any idea is appreciated!