# Q：指数复杂度的具体情况

Let's an algorithm to find all paths between two nodes in a directed, acyclic, non-weighted graph, that may contain more than one edge between the same two vertices. (this DAG is just an example, please I'm not discussing this case specifically, so disregard it's correctness though it's correct, I think).

We have two effecting factors which are:

1. `mc`: max number of outgoing edges from a vertex.
2. `ml`: length of the max length path measured by number of edges.

Using an iterative fashion to solve the problem, where complexity in the following stands for count of processing operations done.

for the first iteration the complexity = mc

for the second iteration the complexity = mc*mc

for the third iteration the complexity = mc*mc*mc

for the (max length path)th iteration the complexity = mc^ml

Total worst complexity is (mc + mc*mc + ... + mc^ml).

1- can we say it's O(mc^ml)?

2- Is this exponential complexity?, as I know, in exponential complexity, the variable only appear at the exponent, not at the base.

3- Are mc and ml both are variables in my algorithm comlexity?

1. `mc`: max number of outgoing edges from a vertex.
2. `ml`: length of the max length path measured by number of edges.

1 -我们可以说它是O（MC -毫升）？

2 -这是指数复杂？我知道，在指数复杂度中，变量只出现在指数，而不是基。

3是MC和ML都是变量，在我的算法复杂度？

There's a faster way to achieve the answer in O(V + E), but seems like your question is about calculating complexity, not about optimizing algorithm.

Yes, seems like it's `O(mc^ml)`
Yes, they bot can be variables in your algorithm complexity

As about the complexity of your algorithm: let's do some transformation, using the fact that a^b = e^(b*ln(a)):

mc^ml = (e^ln(mc))^ml = e^(ml*ln(mc)) < e^(ml*mc) if ml,mc -> infinity

So, basically, your algorithm complexity upperbound is O(e^(ml*mc)), but we can still shorten it to see, if it's really an exponential complexity. Assume that ml, mc <= N, where N is, let's say, max(ml, mc). So:

e^(ml*mc) <= e^N^2 = e^(e^2*ln(N)) = (e^e)^(2*ln(N)) < (e^e)^(2*N) = [C = e^e] = O(C^N).

So, your algorithm complexity will be O(C^N), where C is a constant, and N is something that growth not faster than linear. So, basically - yes, it is exponetinal complexity.

Yes, seems like it's `O(mc^ml)`
Yes, they bot can be variables in your algorithm complexity

MC ^毫升=（E ^ LN（MC））^毫升= E ^（ML×ln（MC））& lt；E ^（ML MC）如果毫升，MC >；无限

E（毫升* MC）& LT；= = 2 = 2（e；2 * LN（n））=（e；E）；（（b））；（e；E；）；（=。

algorithm  time-complexity  complexity-theory