0
$\begingroup$

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?

Improve this question
$\endgroup$
5
  • $\begingroup$ As our reference question explains, for loops are rather easy: translate them into (nested) sums, the simplify. $\endgroup$ – Raphael♦ Nov 29 '17 at 10:41
  • $\begingroup$ Are you after an algorithm? Not sure what the one you're citing is about. I'd go with computer algebra for simplifying sums. $\endgroup$ – Raphael♦ Nov 29 '17 at 10:42
  • $\begingroup$ Yes, I am about finding an algorithm that can parse a program (defined in such a simple language) and calculate it's asymptotic complexity. $\endgroup$ – qvian Nov 29 '17 at 10:58
  • $\begingroup$ Such an algorithm does not exist, at least if you permit all programs. Restricted to only for-loops with "simple" boundaries might work, though. $\endgroup$ – Raphael♦ Nov 29 '17 at 12:48
  • $\begingroup$ Yes, I am aware of the link that you sent me, but I am asking for a specific set of programs (as described above). The solution that was provided to the given (really restricted) problem is essentially an $O(m 2^m)$ solution, where $m$ is the number of for loops (due to counting the number of topological orderings via Dynamic Programming), but that's enough for me. I just wanted to understand the correctness behind this solution. $\endgroup$ – qvian Nov 29 '17 at 12:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.