15,796,738 members
See more:
Python
```
```

l
```list1 = [15, 12, 13, 19, 14]
list2 = [19, 13, 15, 12, 14]

def function(l1, l2):
for i in range(len(list1)):
for j in range(len(list2)):
if list1[i] == list2[j]:
print ('B[' + str(i) + ']' + ' with ' + 'A[' + str(j) + ']')

function(list1, list2)```

How to make a less time complexity algorithm?

What I have tried:

I have tried the above code, but I want another efficient one.
Posted
Updated 3-May-21 10:43am
Richard MacCutchan 3-May-21 9:37am
What is the code supposed to do?
CPallini 3-May-21 9:43am
'Match the indices', of course! :-)
Actually it finds the matching values.
Richard MacCutchan 3-May-21 9:47am
I can see what it is doing, but I do not understand what the objective is.
CPallini 3-May-21 9:55am
I suppose the objective is, precisely, finding matching values.
[no name] 3-May-21 10:13am
I mean in list 1, the first number is 15 (which is at index 0).. the mission is to find the same number in the second list, but printing its index. So, list1 number 15 is at list2 at index 2. and so on..
If you do not know python or java, it does not matter, I just want to know the efficient algorithm to solve this problem. this one takes O(n^2).

## Solution 1

Try the following which may, or may not be more efficient:
Python
```for i in range(len(list1)):
try:
j = list2.index(list1[i])
print ('B[' + str(i) + ']' + ' with ' + 'A[' + str(j) + ']')
except ValueError:
print("no match for", list1[i])
```

[no name] 3-May-21 10:16am
Thank you so much :)
Richard MacCutchan 3-May-21 10:38am
You are welcome, but see CPallini's comment below.
CPallini 3-May-21 10:23am
Should be still O(N^2),according to:
https://wiki.python.org/moin/TimeComplexity
However, the code is nice. Have my 5.
Richard MacCutchan 3-May-21 10:30am
Thanks. I could not see a Big-O value for the index method, although it does reduce the number of iterations in the second loop. The same could be done by a `break` statement in the original.
CPallini 3-May-21 10:33am
'x in s'

## Solution 2

A little improvement, assuming there is only 1 match.
Python
```list1 = [15, 12, 13, 19, 14]
list2 = [19, 13, 15, 12, 14]

def function(l1, l2):
for i in range(len(list1)):
for j in range(len(list2)):
if list1[i] == list2[j]:
print ('B[' + str(i) + ']' + ' with ' + 'A[' + str(j) + ']')
break; # gets out of loop
function(list1, list2)```

Only a little better than O(n²)

There is another approach where complexity is the one of sort function (O(n log(n)).
Python
```list1 = [15, 12, 13, 19, 14]
list2 = [19, 13, 15, 12, 14]
# create a list with indices of list2
list3 = [0, 1, 2, 3, 4]
# then do an indirect sort
# I sort list3 on the values of list2
def sortindirect(elem):
return list2[elem]

list3.sort(key=sortindirect)
# list3 = [4, 1, 3, 0, 2]
def function(l1, l2):
for i in range(len(list1)):
# Then rather that scan list2 for a match, I search list2 using dichotomy
for j in range(len(list2)): # drop this loop and replace with a dichotomy search
if list1[i] == list2[list3[j]]:
print ('B[' + str(i) + ']' + ' with ' + 'A[' + str(j) + ']')```

Dichotomic search - Wikipedia[^]
Binary search algorithm - Wikipedia[^]
Python
```# this print list2 as is
for i in range(len(list2)):
print (list2[i])
# this print list2 sorted
for i in range(len(list3)):
print (list2[[list3[i]])```

v3
CPallini 3-May-21 15:58pm
5.
Patrice T 3-May-21 16:01pm
Thank you
Michel Jakson 3-May-21 16:22pm
Patrice .. Can you explain your code please I do not get it? 'O(nlog(n))'
Patrice T 3-May-21 16:51pm
This is complexity of 'sort'
Michel Jakson 3-May-21 16:52pm
Yes I know, I mean your second code, I do not get it.