OPART time complexity?

[lamtung16]

def opart(sequence, lda):
    y, z = get_cumsum(sequence)                           # O(n)
    sequence_length = len(sequence)                       # O(1)
    C = np.zeros(sequence_length)                         # O(1)
    C[0] = -lda                                           # O(1)
    tau_star = np.zeros(sequence_length, dtype=int)       # O(1)
    for t in range(1, sequence_length+1):                            # O(n)
        V = C[:t] + lda + L(np.arange(1, t+1), t*np.ones(t), y, z)   # O(1) -- L has complexity O(1) -- vectorized operation
        last_chpnt = np.argmin(V)                                    # O(1) or O(log n)?
        C[t] = V[last_chpnt]                                         # O(1)
        tau_star[t] = last_chpnt                                     # O(1)
    return trace_back(tau_star)                           # O(n)

@tdhock, last semester, I presented a comparison between my code OPART function (uses vectorized operations to calculate V) and PELT from rupture (uses a regular for loop to calculate V). With a sequence length of about 40,000, my code runs 200 times faster. I know that all previous papers claim that OPART has a time complexity of O(n^2), but can I consider the time complexity of my OPART code to be O(n) or O(n log n)? I'm just asking out of curiosity; it's not that important.

[tdhock]

opart is quadratic. you claim the line below is constant but it is actually linear (arange)

V = C[:t] + lda + L(np.arange(1, t+1), t*np.ones(t), y, z)   # O(1) -- L has complexity O(1) -- vectorized operation

to follow up about this, you should implement the pelt pruning rule and then submit a pr to ruptures