Problem
Let's say we are given a program and we want to find an algorithm that analyses its asymptotic complexity. This program can only have two types of statements: do_something
and the for
loop. The for
loop is defined as followed.
for <variable> = <from> .. <to>
<body>
The for
loop makes the <variable>
iterate from <from>
to <to>
(except when <from>
is greater than <to>
, then <body>
won't be executed at all)
<body>
must be a statement again (so either for
or do_something
).
<variable
> is a lowercase letter a..z
except for n
, which is defined prior to the program.
<from>, <to>
can be any variables defined in the outer loop. Addtionally, <from>
can have the value 1 and <to>
can be n
.
Example:
for i = 1 .. n
for j = 1 .. i
for k = j .. n
do_something
Let $f(n)$ be the number of times do_something
is executed as a function of $n$. We want to know the asymptotic complexity of $f(n)$. For a non-negative integer $k$ and a positive rational $C$, we say that $C \cdot n^k$ is the asymptotic complexity of $f(n)$ if:
$\lim_{n \rightarrow \infty} \frac{f(n)}{C \cdot n^k} = 1$
In the above's example, the asymptotic complexity would be $\frac{1}{3}n^3$.
Solution (?)
I could not come up with an efficient algorithm to solve this problem so I looked it up (which was in a foreign language). However, I only understand a portion of it:
Every
for
loop will give us inequalities:for i = j .. k
means that $j \leq i$ and $i \leq k$. First create a directed graph where each variable corresponds to one node and for every inequality $i \leq j$ we create a directed edge from node $i$ to node $j$. If we consider the strongly connected components (SCC) then we can notice that if two variables $i, j$ are in the same SCC, they must be equal. Now let's consider the condensed graph G' (meaning that we consider every SCC as one node) and let the number of nodes be $m$. The time complexity would be $C \cdot n^m$, where $C = \frac{\text{number of topological sorting in G'}}{m!}$
So I understand that $f(n)$ is a polynomial of degree $m$, but can not explain how the the coefficient of $n^m$ should have the $C$ as described above. Can anyone help me understand this solution?
for
loops are rather easy: translate them into (nested) sums, the simplify. $\endgroup$ – Raphael♦ Nov 29 '17 at 10:41