> It’s quite easy to show that the singing time is Θ(n2); in particular,the singer mentions the name of a gift ∑ni=1i=n(n+1)/2times (counting thepartridge in the pear tree).
I'm pretty sure that I still remember how to read the formula and I even know what does Θ(n2) means, but it's still unclear for me how do we get n^2 and this formula from the "NDaysOfChristmas(gifts[2..n]):" example.
An example: http://jeffe.cs.illinois.edu/teaching/algorithms/book/Algori... Page 15
> It’s quite easy to show that the singing time is Θ(n2); in particular,the singer mentions the name of a gift ∑ni=1i=n(n+1)/2times (counting thepartridge in the pear tree).
I'm pretty sure that I still remember how to read the formula and I even know what does Θ(n2) means, but it's still unclear for me how do we get n^2 and this formula from the "NDaysOfChristmas(gifts[2..n]):" example.