Subject: Binary Tree Roll Algorithm, time complexity, theoretical analysis, empirical analysis
Year: 2016
Type: Article
Title: Time complexity analysis of the binary tree roll algorithm
Author: Bozhinovski, Adrijan
Author: Tanev, George
Author: Stojchevska, Biljana
Author: Pachovski, Veno
Author: Ackovska, Nevena
Abstract: This paper presents the time complexity analysis of the Binary Tree Roll algorithm. The time complexity is analyzed theoretically and the results are then confi rmed empirically. The theoretical analysis consists of fi nding recurrence relations for the time complexity, and solving them using various methods. The empirical analysis consists of exhaustively testing all trees with given numbers of nodes and counting the minimum and maximum steps necessary to complete the roll algorithm. The time complexity is shown, both theoretically and empirically, to be linear in the best case and quadratic in the worst case, whereas its average case is shown to be dominantly linear for trees with a relatively small number of nodes and dominantly quadratic otherwise.
Publisher:
Relation: International Journal of Computer Applications
Identifier: oai:repository.ukim.mk:20.500.12188/24211
Identifier: http://hdl.handle.net/20.500.12188/24211
