SPACE COMPLEXITY ANALYSIS OF THE BINARY TREE ROLL ALGORITHM
Journal Title: Journal of Information Technology and Application (JITA) - Year 2017, Vol 7, Issue 1
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 confi rmed 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.
Authors and Affiliations
A. Božinovski, G. Tanev, B. Stojčevska, V. Pačovski, N. Ackovska
Keywords
Related Articles
- EP ID EP226515
- DOI 10.7251/JIT1701009B
- Views 157
- Downloads 0
USING DECISION TREE CLASSIFIER FOR ANALYZING STUDENTS’ ACTIVITIES
In this paper students’ activities data analysis in the course Introduction to programming at Faculty of Electrical Engineering in East Sarajevo is performed. Using the data that are stored in the Moodle database combine...
E-MAIL FORENSICS: TECHNIQUES AND TOOLS FOR FORENSICINVESTIGATION OF ONE COURT CASE
E-mail has emerged as the most important application on the Internet for communication of messages, delivery of documents and carrying out transactions and is used not only from computers, but many other electronic gadge...
PERFORMANCE EVALUATION OF ROUTING PROTOCOLS IN A WIRELESS SENSOR NETWORK FOR TARGETED ENVIRONMENT
This paper investigates the performance of reactive and proactive routing protocols in a wireless sensor network for targeted enviroment. AODV and DSR are chosen as representatives for the reactive routing protocols and...
CUSTOMER SATISFACTION AS A SIGNIFICANT MEASURE OF SUCCESSFUL ERP IMPLEMENTATION
The measuring of implemented ERP system’s effi ciency is in any case multidimensional. Various researchers dedicated a lot of attention trying to fi nd the best way to measure the success or the effectiveness of ERP solu...
Influence of Infor matio n Tec hnologies on the Company’s Competiti ve Advantage on the Market in Conditio ns of the Global Crisis
In the recent decades, there has been recorded a great expansion in the computing and communication field and all the predictions are pointing to the further technological progress when using information technologies (IT...