Computational complexity based on stopping time

Question

I need help determining the asymptotic computational complexity of a Gibbs sampling algorithm. I believe this algorithm is related to stopping time, but I know very little about stopping time problems. I will now describe the algorithm: For $i = 1, 2, \dots, n$, we define $m+1$ binary random variables (RVs) $A_{i}^{1:m+1} \triangleq A_{i}^{1}, A_{i}^{2}, \dots, A_{i}^{m+1}$, where $m \in \mathbb{N}$. We wish to generate samples from the joint distribution $P(A)$ using Gibbs sampling, where $A \triangleq A_{1}^{1:m+1}, A_{2}^{1:m+1}, \dots A_{n}^{1:m+1}$ denotes all RVs. The current sample is represented by the array \begin{align} \mathbf{S} = \begin{bmatrix} A_{1}^{1} & A_{1}^{2} & A_{1}^{3} & \cdots & A_{1}^{m+1} \\ A_{2}^{1} & A_{2}^{2} & A_{2}^{3} & \cdots & A_{2}^{m+1} \\ \cdots & \cdots & \cdots & \cdots & \cdots \\ A_{n}^{1} & A_{n}^{2} & A_{n}^{3} & \cdots & A_{n}^{m+1} \\ \end{bmatrix}, \end{align} and it is generated using the following two rules:

1. At most one variable per row may equal one, and the rest must equal zero. If $A_{i}^{j} = 1$, then $A_{i}^{k} = 0$ for all $k \neq j$.
2. Beyond the first column, at most one variable per column may equal one, and the rest must equal zero. Multiple entries in the first column may equal one at once. More concisely: If $A_{i}^{j} = 1$ and $j > 1$, then $A_{k}^{j} = 0$ for all $k \neq i$.

Given the remaining variables states $A_{\setminus(i, j)}$, these rules result in the following two conditional distributions over $A_{i}^{j}$:

1. If it is possible for $A_{i}^{j}$ to equal $1$, then the conditional distribution is given by \begin{align} P(A_{i}^{j} | A_{\setminus (i, j)}) = \begin{cases} 1 - q_{i}^{j}, \ & \ \text{if } A_{i}^{j} = 0 \\ q_{i}^{j}, \ & \ \text{if } A_{i}^{j} = 1 \end{cases}, \end{align} where $q_{i}^{j} \in [0, 1].$ We sample from the above distribution in two cases: a) Row $i$ is otherwise empty, and column $j > 1$ is otherwise empty. b) Row $i$ is otherwise empty, and $j = 1$.

2. If it is not possible for $A_{i}^{j}$ to equal one, then $P(A_{i}^{j} = 0 | A_{\setminus(i, j)}) = 1$. This occurs if row $i$ is otherwise occupied, and column $j > 1$ is otherwise occupied. In these cases, we obviously do not need to sample from the conditional distribution.

Based on the above, we generate a sample by iteratively sampling across the rows of $\mathbf{S}$, and we can avoid sampling from most variables. We now consider the following example: The previous iteration of Gibbs sampling produced the sample $\mathbf{\hat{S}}$, where $\hat{A_{i}^{j}} = 1$ and $j > 1$. This implies every other entry in row $i$ is zero, and every other entry in column $j$ is zero. When we sample from row $i$, we can skip sampling from the variables $A_{i}^{1:j-1}$ as they must equal zero. We can jump to column $j$ and sample from $P(A_{i}^{j} | A_{\setminus (i, j)})$ by flipping a weighted coin. If $A_{i}^{j} = 1$, then we can stop sampling from row $i$, as the variables $A_{i}^{j+1:m+1}$ must all equal zero. However, if $A_{i}^{j} = 0$, then we must sample from the variables $A_{i}^{j+1:m+1}$ until we obtain a one. If we obtain a one, then we can stop sampling.

We initialise the algorithm by setting $\mathbf{S}$ to be an $n \times (m+1)$ array of zeros. The algorithm can be implemented using the following Matlab code:

%% Variable setup
numberOfSamples = 1000;
n = 20;
m = 20;
rowIndicator = zeros(n, 1);
columnIndicator = zeros(1, m+1);
q = rand(n, m+1);
%% Gibbs sampling
for sample = 1:numberOfSamples
    for i = 1:n
        %% Starting point
        k = rowIndicator(i) + (rowIndicator(i) == 0);
        %% Sample from remaining variables
        for j = k:(m+1)
            if ((columnIndicator(j) == 0) || (columnIndicator(j) == i))
                if (rand < q(i, j))
                    %% We have obtained a one, we can stop sampling
                    columnIndicator(j) = i * (j > 1);
                    rowIndicator(i) = j;
                    break; 
                else
                    %% We have obtain a zero, we must continue sampling
                    columnIndicator(j) = 0;
                    rowIndicator(i) = 0;
                end
            end
        end
    end
end

We do not explicitly create a sample array $\mathbf{S}$, the variables rowIndicator and columnIndicator keep track which rows and columns of $\mathbf{S}$ are currently occupied. If rowIndicator(i) = 0, the row $i$ is unoccupied. Similarly, if columnIndicator(j) = 0, then column $j$ is unoccupied, where we always have columnIndicator(1) = 0.

Is it possible to determine the asymptotic computational complexity of this algorithm? How many times do we flip a weighted coin in this algorithm? I believe the algorithm is linear in $n$, and linear in the number of samples we wish to produce. In what way is the algorithm's computational complexity a function of $m$?