1
$\begingroup$

I'm trying to wrap my head around how to calculate the time complexity of algorithms that exhibit factorial (𝑛!) or exponential (2^𝑛) growth rates.

Specifically, I want to understand the thought process behind arriving at these time complexities.

  1. How do experts determine that an algorithm's time complexity is factorial (𝑛!) or exponential (2^n)?

  2. Are there any key indicators or patterns in the algorithm's structure or operations that suggest these complexities?

I'm particularly confused when trying to calculate the time complexity of algorithms that explore all possible paths in a graph.

$\endgroup$

2 Answers 2

2
$\begingroup$

All possible paths in a graph: If all nodes are connected, you have 100 nodes, and the start node is given, you can move to one of 99 nodes. If you don't want to visit the same node twice, you can visit 98 nodes as the second node from each first node, total 99 x 98. Each path to the second node lets you take 97 paths to the third node, that's 99 x 98 x 97. Quite obviously factorial in the number of nodes.

The most important question is: How does the work required change if the problem size changes? If you are lucky, then you can restrict the growth, but if increasing the problem size by 1 increases the time by a constant factor c > 1 or more, then you have exponential growth.

In practice, just implement the algorithm and run it with growing problem size. Construct a "travelling salesman" problem with varying number of cities from 1 to 10000, set it up with random distances, and solve it. How fast does the execution time grow with the number of cities? What's the largest problem you can solve in a day?

$\endgroup$
1
$\begingroup$

I'm particularly confused when trying to calculate the time complexity of algorithms that explore all possible paths in a graph.

Consider a graph $G$ of $n$ vertices. Assuming all pairs of vertices are connected via an edge (i.e. $G$ is complete), then a path $v_1v_2\dots v_n$ can be any permutation of the $n$ vertices. Hence, there exist $n!$ possible paths in $G$ since we have $n$ choices to pick the first vertex, $n-1$ choices for the second, and so on.

An algorithm often exhibits a factorial time complexity when it iterates through all permutations of a certain set of elements (such as vertices in a graph). An algorithm often runs in $\mathcal{O}(2^n)$ when it iterates through all possible subsets of a set of elements (such as a solver to SUBSET-SUM).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.