I’m currently working through *Algorithms* by Dr. Jeff Erickson. The following is an algorithm presented in the book:

`NDaysOfChristmas(gifts[2 .. n]): for i ← 1 to n Sing “On the ith day of Christmas, my true love gave to me” for j ← i down to 2 Sing “j gifts[j],” if i > 1 Sing “and” Sing “a partridge in a pear tree.” `

Here’s the runtime analysis of the algorithm presented by Dr. Erickson:

The input to

NDaysOfChristmasis a list of $ n − 1$ gifts, represented here as an array. It’s quite easy to show that the singing time is $ \Theta(n^{2})$ ; in particular, the singer mentions the name of a gift $ \sum_{i=1}^ni = \frac{n(n + 1)}{2}$ times (counting the partridge in the pear tree). It’s also easy to see that during the first $ n$ days of Christmas, my true love gave to me exactly $ \sum_{i=1}^{n}\sum_{j=1}^{i}= \frac{n(n + 1)(n + 2)}{6} = \Theta(n^3)$ gifts.

I can’t seem to grasp how it is possible your $ “$ true love$ “$ had given you $ \Theta(n^3)$ gifts, while a computer scientist looking at this algorithm would say the algorithm’s runtime complexity is $ \Theta(n^2)$ ?

Dr. Erickson also says the name of a gift is mentioned $ \frac{n(n+1)}{2}$ times, which is in $ \Theta(n^2)$ .