Worst Case Optimal Union-Intersection Expression Evaluation | Zendy

Ehsan Chiniforooshan | Zendy; Arash Farzan | Zendy; Mehdi Mirzazadeh | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Worst Case Optimal Union-Intersection Expression Evaluation

Author(s) -

Ehsan Chiniforooshan,

Arash Farzan,

Mehdi Mirzazadeh

Publication year - 2005

Publication title -

lecture notes in computer science

Language(s) - English

Resource type - Book series

SCImago Journal Rank - 0.249

H-Index - 400

eISSN - 1611-3349

pISSN - 0302-9743

ISBN - 3-540-27580-0

DOI - 10.1007/11523468_15

Subject(s) - intersection (aeronautics) , expression (computer science) , computer science , upper and lower bounds , set (abstract data type) , algorithm , mathematical optimization , discrete mathematics , mathematics , mathematical analysis , engineering , programming language , aerospace engineering

We consider the problem of evaluating an expression consisting of unions and intersections of some sorted sets. Given the expression and the sizes of the sets, we are interested in the worst-case complexity of evaluating the expression in terms of the sizes of the sets. We assume no set is repeated in the expression. We show a lower bound on this problem and present an algorithm that matches the lower bound asymptotically.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research