Cybernetics And Systems Analysis logo
Editorial Board Announcements Abstracts Authors Archive
Cybernetics And Systems Analysis
International Theoretical Science Journal
UDC 004.655
V.N. Red’ko,1 D.B. Buy,2 I.S. Kanarskaya,3 A.S. Senchenko4

PRECISE ESTIMATES OF THE TIME COMPLEXITY OF IMPLEMENTING
THE ALGORITHMS OF SET-THEORETIC OPERATIONS IN TABLE ALGEBRA

Abstract. The algorithms implementing intersection, union, and difference in table algebras are investigated. Modifications of the most common algorithms reducing the amount of computation are proposed. Based on the evaluated complexities in the worst case and in the average for the modified algorithms, the fastest algorithm for each operation is found. The program experimentally confirming the theoretical estimates is developed.

Keywords: complexity of algorithms, database, table algebra.



FULL TEXT

1Taras Shevchenko National University of Kyiv, Kyiv, Ukraine

2Taras Shevchenko National University of Kyiv, Kyiv, Ukraine,
e-mail: dmitriybuy@mail.ru; buy@unicyb.kiev.ua.

3Taras Shevchenko National University of Kyiv, Kyiv, Ukraine,
e-mail: Iren_kiss@mail.ru.

4Taras Shevchenko National University of Kyiv, Kyiv, Ukraine,
e-mail: senchenko_as@mail.ru.

© 2017 Kibernetika.org. All rights reserved.