# 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)$$.