It took a ton of work and a whole lot of headaches but I finally understand the math behind the Aggregate Method calculation for amortized time. The final step I did not understand related to a property of logarithms where a logarithm as an exponent that shares the same base is in fact equivalent to the value within the logarithm. It feels great to have overcome this problem. I know it may be pointless in the grand scheme of things but overcoming obstacles is always beneficial. At least I think so.
TLDR;
Okay, so here are the highlights of what I did:
- I finally finished breaking down the Aggregate Method. I found the comments for this article from Geeks for Geeks to be very helpful. I found one particular comment thread to be very interesting. It covered a mathematical breakdown of the resizing cost. It used the formula for calculating the sum of a geometric progression. I got through the final step after a ton of work. I guess I never really learned logarithms like I should. I should probably take some university level math courses on my own to make sure this type of situation doesn’t happen again.
- I cleaned up a bunch of browser tabs, having finished working through my current problem. What a feeling of relief. I saved all the useful links and I now have to formalize my notes in a clear and concise way that I can refer back to if I need to in the future. It’s not very fun but it sure beats hitting my head against the wall trying to figure out what I am doing wrong. LOL.
Useful Links for Amortized Analysis
- What are Asymptotes?
- Asymptotic analysis
- Big O Notation (MIT)
- Amortized Analysis
- Lecture notes on Amortized Analysis – Cornell University
- Lecture on Amortized Analysis – UC Berkley (Has a video)
- Article on Amortized Analysis (Aggregate Method Example)
- Introduction to Logarithmic Functions
- Summation Formulas and how they work
- Exponent Rules in Math
- Solving logarithm problems in Math
- Geometric Progressions in Math (Sum equations for GPs)
- Logarithms problem solution (How to prove 2 ^ log n is equal to n)
Conclusion
That’s all for today. If you are interested in the MIT course you can check out the video lecture I’m currently going through. The lecture is helpful but isn’t sufficient by itself. Anyways, until next time PEACE!