Knuth's famous paper "The Complexity of Songs" (1977) deserves a mention. He describes how most songs of length n require a text of length proportional to n. But he goes on to prove the complexity of Old MacDonald had a farm as O(sqrt(n)), the complexity improvement of Twelve days of Christmas, the O(log n) song 99 bottles of beer on the wall, and finally the O(1) song That's the way I like it by KC and the Sunshine Band.
https://dl.acm.org/doi/pdf/10.1145/1008354.1008355
Also, the linked Science article is just a summary. The full paper (not paywalled) is at: https://www.nature.com/articles/s41598-024-55742-x