15,942,710 members
See more:
My givens are:

- a list of N rna sequences (in string form) W = [W0, W1, W2, ..., W(n-1)]

- a list of M queries, Q = [(i, j), (i1, j1), (i2, j2), ..., (iN, jN)] (each 0 <= i & each j < N = len(W))

- if W_i & W_j have different lengths, assume W_i < W_j

Prompt: write a function less_than(W, Q) that returns whether W_i is less than W_j in alphabetical order, for each query

What I have tried:

Python
```def less_than(W, Q);
return [W[i] < W[j] for i, j in Q]```

- I know this solution is a correct implementation, but according to one person I had review the code, it has O(n^2) (quadratic) time complexity, and from another, I was told the code has O(MN) complexity. I'm not sure if there is a way to further improve the time complexity of the current solution.
Posted
Updated 12-Mar-22 4:53am
v2

Solution 1

To me, it appears this code has a complexity of O(M*N), as it is linear with respect to string length and iteration through i & j together is also linear. I am not sure if the code can be further optimized.