search

jeffgerickson / algorithms

Bug-tracking for Jeff's algorithms book, notes, etc.
7.92k stars 1.02k forks source link

Ch0.6 p15 NDaysOfChristmas #67

Closed MarkJeronimus closed 5 years ago

MarkJeronimus commented 5 years ago

The running time should probably be Θ(2), not Θ(3)

MarkJeronimus commented 5 years ago

Oops I meant O(n^2)

jeffgerickson commented 5 years ago

That's what it says on page 15: "It’s quite easy to show that the singing time is Θ(n^2); in particular, the singer mentions the name of a gift n(n + 1)/2 times (counting the partridge in the pear tree)." But the number of gifts is Θ(n^3).