Please use this identifier to cite or link to this item:
http://hdl.handle.net/20.500.12188/24211
Title: | Time complexity analysis of the binary tree roll algorithm | Authors: | Bozhinovski, Adrijan Tanev, George Stojchevska, Biljana Pachovski, Veno Ackovska, Nevena |
Keywords: | Binary Tree Roll Algorithm, time complexity, theoretical analysis, empirical analysis | Issue Date: | 1-Dec-2016 | Journal: | International Journal of Computer Applications | 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. | URI: | http://hdl.handle.net/20.500.12188/24211 |
Appears in Collections: | Faculty of Computer Science and Engineering: Journal Articles |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
2900-Article Text-6294-1-10-20170104.pdf | 461.98 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.