undefined

2.6.3. The traditional Christmas carol The 12 Days of Christmas has the following struc- ture: On day 1, the singer gets one gift of type 1 (a partridge in a pear tree) from their true love; on day 2, the singer gets two gifts of type 2 and one gift of type 1 (two turtledoves and a partridge in a pear tree); and so on. Suppose this song can be extended to any arbitrary number of days. (a) Give a big-O estimate of the time it takes to sing verse n, occurring on day n, as a function of n. (Assume that it takes the same length of time to sing about each gift, e.g., the eight maids a-milking takes the same length of time as the two turtledoves, which in turn takes the same amount of time as whatever is gifted on day 2739.) (b) Give a big-O estimate of the time it takes to sign the entire song, starting with verse 1 on day 1, and going all the way to verse n on day n. 2.6.3. The traditional Christmas carol The 12 Days of Christmas has the following struc- ture: On day 1, the singer gets one gift of type 1 (a partridge in a pear tree) from their true love; on day 2, the singer gets two gifts of type 2 and one gift of type 1 (two turtledoves and a partridge in a pear tree); and so on. Suppose this song can be extended to any arbitrary number of days. (a) Give a big-O estimate of the time it takes to sing verse n, occurring on day n, as a function of n. (Assume that it takes the same length of time to sing about each gift, e.g., the eight maids a-milking takes the same length of time as the two turtledoves, which in turn takes the same amount of time as whatever is gifted on day 2739.) (b) Give a big-O estimate of the time it takes to sign the entire song, starting with verse 1 on day 1, and going all the way to verse n on day n