Time complexity analysis of the binary tree roll algorithm
Journal
International Journal of Computer Applications
Date Issued
2016-12-01
Author(s)
Bozhinovski, Adrijan
Tanev, George
Stojchevska, Biljana
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.
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.
Subjects
File(s)![Thumbnail Image]()
Loading...
Name
2900-Article Text-6294-1-10-20170104.pdf
Size
461.98 KB
Format
Adobe PDF
Checksum
(MD5):cd3bfc4b5940803bfc071c83e7006ce8