How to Reconcile Apparent Discrepancy in this Algorithm’s Runtime?


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 NDaysOfChristmas is 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)$.