Click here to Skip to main content
15,942,710 members
Please Sign up or sign in to vote.
0.00/5 (No votes)
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

1 solution

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.
 
Share this answer
 
Comments
Selecaoinha1179 12-Mar-22 17:16pm    
would using mapping optimize the code?

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900