Question: I was going through a past paper question but I don't have any answers to know if I'm working out the problems correctly or not.

I need to find the time complexity for:

```
i) repeat
      n:=n div 2;
   until n=1;

ii) for i:=1 to n do
       begin
          for j:=1 to n do
             begin
                for k:=1 to n do;
             end;
       end;

iii) repeat
        for i:=1 to n do
           begin
              for j:=1 to n do;
           end;
     n:=n div 2
     until n=1

```

In my opinion, the answer for (ii) is $O(\log n)$ and the answer for (ii) is $O(n^3)$ but I'm not sure about my answers. Regarding question (iii) I have no idea how to come up with a solution.

Answer: 
This problem is an instance of the [list coloring](https://en.wikipedia.org/wiki/List_coloring) problem. The list coloring problem is a variant of the graph color problem, where additionally have constraints that provide for each vertex a list of allowable colors that can be used for that vertex.

Here's the relationship. Let $V$ denote the set of distinct values that appear in any row. In Example 1, $V=\{A,B,C,D,E\}$; in Example 2, $V=\{A,B,C,D\}$. Form an undirected graph $G$ where $V$ is the vertex set (so each value is a vertex). Add an edge $(u,v)$ between two values if there is some row where those two vertices appear together.

Now suppose we want to arrange these in a matrix with $c$ columns (i.e., $c$ is the length of the longest row). We'll imagine having $c$ colors, numbered from $1$ to $c$, where color $i$ corresponds to the $i$th column. If the value $v$ is colored $i$, we take this to mean that every appearance of value $v$ should appear in column $i$.

Now from each row that is less than $c$ values long, we obtain some constraints. In particular, if we have a row that is $\ell$ values long, then each value in that row needs to be colored with a color in the set $\{1,2,\dots,\ell\}$ (to ensure the lower-triangular requirement). These are the lists that make this a list coloring problem.

Now any solution to the list coloring problem yields a solution to your problem: the colors tell you what column to put each value into, which tells you how to permute each of your rows to form a valid solution. Therefore, you can use any algorithm for the list coloring problem to solve your problem.
To solve this problem in practice, here's the first thing I would try:

* Try using a SAT solver.

As long as your problem instance isn't too large, I suspect that a SAT solver will be very effective at solving this problem.

Here is how you use a SAT solver. Introduce boolean variables $x\_{v,j}$ (where $v$ ranges over values, and $j$ ranges over columns). If your original matrix has $n$ distinct values and the longest row has $c$ columns, you'll have $cn$ boolean variables ($v$ ranges over $n$ distinct values, and $j$ ranges from $1$ to $c$). The intended meaning of $x\_{v,j}$ is that value $v$ appears only in column $j$.

Now add boolean constraints as follows:

* If the value $v$ appears somewhere in the input, then it needs to appear in some row. This gives us the constraint $x\_{v,1} \lor x\_{v,2} \lor \dots \lor x\_{v,c}$ for each value $v$.
* If the value $v$ appears in a row of length $\ell$, then the value $v$ must appear in one of the first $\ell$ columns. Consequently, for each $v$ we get the constraint $x\_{v,1} \lor x\_{v,2} \lor \dots \lor x\_{v,\ell}$, where $\ell$ is the length of the shortest row containing the value $v$. (This actually subsumes the constraint in the previous bullet, so that one can be omitted.)
* The value $v$ appears in at most one column. This gives us the constraint $\neg x\_{v,j} \lor \neg x\_{v,k}$ for each value $v$ and each pair $j,k$ of columns (where $1 \le j < k \le c$).
* If there is some row that contains both the value $u$ and the value $v$, then both $u$ and $v$ cannot be placed into the same column. Consequently, we get the constraint $\neg x\_{u,j} \land \neg x\_{v,j}$ for each $j=1,2,\dots,c$ and each pair of values $u,v$ that appear together in the same row.

Then let the SAT solver crank away. Give it a try -- I think it might just work on the problems you have in practice.

To learn more about using SAT solvers to solve graph coloring problems, see, e.g., [this nifty video](https://www.youtube.com/watch?v=0gt503wK7AI).