Growing Arrays
Growing Arrays: The Ninth Song Won't Fit: Growing Arrays, Is Adding a Song Slow? Amortized Cost, Why Does This Loop Take Seconds? Your Language's List.
Updated
- The Ninth Song Won't Fit: Growing Arrays (Apprentice): A playlist of 8 slots crashes on the 9th song. Find a way to let it grow to a million songs without every add slowing down, and meet the structure inside every language's list: the growing array.
- Is Adding a Song Slow? Amortized Cost (Journeyman): One add to a growing playlist just copied 1,024 songs. Work out what adding really costs over a long run of adds, why doubling beats growing a little at a time, and what "amortized O(1)" promises.
- Why Does This Loop Take Seconds? Your Language's List (Apprentice): A loop over 100,000 orders takes seconds, and one call in it is why. Meet your language's list, the growing array under five names, and read its cost card before you pick a method.