I am learning algorithm analysis and I have come across a problem.
What I Have Done
I wrote a program that generates 30 binary trees of random size where each node of each tree has random value. Now In order to use amortized analysis I assigned (as required) a rank to each node of the tree as following
" If the rank of a node is r, then the rank of its left child is r −1 and the rank of its right child is r + 1. "
Now to define amortized complexity of each node I converted the following equation into a c++ code
"ai = ti + Φ(Si) − Φ(Si−1)" , where Si−1 is the state of D just before the ith call begins, and Si is the state of D just after it has finished.
What's Remaining
I have to compare the experimental results to the estimation of the amortized analysis.
I am blind at this part and don't know what to do. Anybody good at it or just push me in the in the right direction. I can't find help anywhere else.