Optimize algo to check if records exists, else skip

user_9888183 0
Viewed 79

Is there a way to can optimize the algo to O(Log n). Given a List check if records exists between the items. If no records exists then drop the item.

sample code:

l1 = [A,B,C,D]

foreach item1 in l1: 
  foreach item2 in l1:
     is_exist=funcCheckRecordsExists(item1,item2)

So if no records exists for item (A,B) then no records exists between (B,A) as well. so when I have element items as (B,A) it should skip the function call. is it possible to reduce the time complexity from O(n*n) to O(log n)?

data-structures time-complexity list python
1 Answers

The best solution in your exemple is (n + 1) x n / 2.

There are 6 commbination of 2 elements in 4. A formule is : 4! / ( 2! x (6 - 4)! ) = 4x3x2x1 / (2x1 x 2x1) = 4x3 / 2 = 6

And more there are 4 elements (X, X) with X in [A, B, C, D]

The solution is 10 elements for your exemple.

If i generalize, we are n!/(2!(n-2)!) + n.

With a combination where 2 elements in n : n!/(2!x(n-2)!)

And n elements with structure (X, X)

The algorithme is :

list = [A, B, C, D]
for i in list:
    list.pop(i)
    for j in list:
        is_exist=funcCheckRecordsExists(i,j)

Best regard,

user_70846820
Related