Big O for the case of exponential complexity
Let the algorithm find all paths between two nodes in a directed, acyclic, unweighted graph that can contain more than one edge between the same two vertices. (this DAG is just an example, please, I am not discussing this case specifically, so do not overlook it correctly, although it is correct I think).
We have two influencing factors:
-
mc
: the maximum number of outgoing edges from the vertex. -
ml
: length of the path of the maximum length, measured by the number of edges.
Using an iterative way to solve the problem, where the complexity in the following means the number of processing operations performed.
for the first iteration, complexity = mc
for the second iteration, complexity = mc*mc
for the third iteration, complexity = mc*mc*mc
for path (max length) iteration complexity = mc^ml
Overall worst difficulty (mc + mc*mc + ... + mc^ml)
.
1- can we say it O(mc^ml)
?
2- Is this exponential complexity? As I know, in exponential complexity, the variable only appears at the exponent and not at the base.
3- Are mc
and ml
both are variables in my algorithm complexity?
source to share
There is a faster way to get the answer in O(V + E)
, but it looks like your question is about calculating the complexity, not about optimizing the algorithm.
Yes, it looks like it O(mc^ml)
Yes, they can be variables in the complexity of your algorithm
As with the complexity of your algorithm: do some conversion 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, an upper bound on the complexity of the algorithm O(e^(ml*mc))
, but we can still shorten it to see if it really is exponential complexity. Suppose that ml, mc <= N
, where N, 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 constant, but N
is that growth is not faster than linear. So basically - yes, this is the complexity of the exponent.
source to share