Longest common subsequence of a set of sequences There is as input a set of $m$ sequences of length $n$.

I thought it was pretty straightforward at first that the time complexity of the algorithm provided below is $O(m^2n^4)$ but then it occurred to me that the time taken depends on the length of a LCS such that the longer a LCS relative to the input length the shorter the computation.
The question I have is can you confirm that while the (measured) time taken does depend on the length of a LCS (inversely), that fact does not have an effect on the result of the O-analysis?

// Let there be m sequences of lenght n.

// Length of lcs of two sequences. Theta(n^2)
lcs_length(x, y)
// Edit distance of two sequences. Theta(n^2)
d(x, y) = |x| + |y| - 2*lcs_length(x, y)
// Edit distance (total) of y to all of X. Theta(mn^2)
d(X. y) = sum of d(x, y) for x in X

// Longest common subsequence of a set of sequences S. O(m^2n^4)
lcs(S)
    X &lt;- copy of S
    while true
        if exists x in X: |x| = 0
            return ""
        if exists x in X: for all s in S: x is a subsequence of s
            return x
        for x in X
            d_min &lt;- +infinity
            i_min &lt;- +infinity
            for i in 1..|x|
                // Make a copy of x with the ith symbol removed:
                x_i &lt;- x[0..i-1] + x[i+1...]
                // Compute the sum of edit distances to all of the original sequences:
                d_i &lt;- d(S, x_i)
                if d_i &lt; d_min
                    d_min &lt;- d
                    i_min &lt;- i
        X &lt;- X difference { x }
        X &lt;- X union { x[0..i_min-1] + x[i_min + 1...] }
There may be multiple different ways to upper-bound the running time of an algorithm.

Saying that the running time of an algorithm is $O(m^2 n^4)$ is analogous to saying that the running time is at most $m^2 n^4$ (ok, $c \cdot m^2 n^4$, for some constant $c$).  The keyword there is "at most".  So, think of $O(\cdot)$ as more like $\le $ than like $=$.

I haven't tried to analyze the running time of your specific algorithm, but to make up some numbers, it is possible that the running time could simultaneously be $O(m^2 n^4)$ and it could also be true that the running time is (say) $O(m^2 \ell^4)$ where $\ell$ is the length of the longest subsequence.  I'm totally making up those figures -- don't take them too seriously, as I don't claim they are actually valid running times for your algorithm -- I am just saying that both claims are consistent, i.e., they could both be true, without contradicting each other.

It's analogous to the fact that we could have both $x \le 3$ and $x \le 4$ be true.  Or, we could have both $x \le c^2$ and $x \le d^3$ be true.



Side remark: I haven't looked at your algorithm closely, but it looks suspicious to me. I would be surprised if it is a correct solution for the longest common subsequence problem.