Space Complexity Analysis of the Binary Tree Roll Algorithm

Authors

  • Adrijan Božinovski School of Computer Science and Information Technology, University American College Skopje
  • George Tanev School of Computer Science and Information Technology, University American College Skopje
  • Biljana Stojčevska School of Computer Science and Information Technology, University American College Skopje
  • Veno Pačovski School of Computer Science and Information Technology, University American College Skopje
  • Nevena Ackovska Faculty of Computer Science and Engineering, University “Sv. Kiril i Metodij”, Skopje

DOI:

https://doi.org/10.7251/JIT1701009B

Abstract

This paper presents the space complexity analysis of the Binary Tree Roll algorithm. The space complexity is analyzed theoretically and the results are then confirmed empirically. The theoretical analysis consists of determining the amount of memory occupied during the execution of the algorithm and deriving functions of it, in terms of the number of nodes of the tree n, for the worst - and best-case scenarios. The empirical analysis of the space complexity consists of measuring the maximum and minimum amounts of memory occupied during the execution of the algorithm, for all binary tree topologies with the given number of nodes. The space complexity is shown, both theoretically and empirically, to be logarithmic in the best case and linear in the worst case, whereas its average case is shown to be dominantly logarithmic.

Published

2017-06-29

Issue

Section

Чланци