0
$\begingroup$

If I have a list of conditions:

and(a,or(b,c))
not(b)
or(a,c)
and(a,d)
or(or(or(a,b),c),d)

and I'm given values for these conditions, let's say, a=true, b=false, c=false, d=true, what is a good algorithm to find the true ones in less than O(log n)? I'm trying to avoid testing all conditions.

A good context for this problem would be wireshark trying to check for filters for every possible part of the currently parsed packet

$\endgroup$
1
  • 1
    $\begingroup$ If there is one true between multiple OR, you can short circuit as true. If there is one false between multiple AND, you can short circuit as false. I think the worst case is O(n), since you could have a lot of AND and a lot of true. $\endgroup$ Commented Feb 18 at 15:26

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.