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 <- 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 <- +infinity            i_min <- +infinity            for i in 1..|x|                // Make a copy of x with the ith symbol removed:                x_i <- x[0..i-1] + x[i+1...]                // Compute the sum of edit distances to all of the original sequences:                d_i <- d(S, x_i)                if d_i < d_min                    d_min <- d                    i_min <- i        X <- X difference { x }        X <- X union { x[0..i_min-1] + x[i_min + 1...] }
Longest common subsequence of a set of sequences
algorithms;time complexity;subsequences