Question

A couple years ago, Kyle started watching "Parks and Office Places", a network television series that remains entertaining even after rewatching episodes multiple times. Each episode of the series is exactly 20 minutes long, and each season of the show features exactly 13 episodes. In anticipation for new seasons, Kyle likes to watch every episode of every previous season before beginning the new season's episodes. Suppose the show continues for n seasons and the title of each episode is stored in two- dimensional array titles(1..n, 1..13) where titlej, k) is the title of the kth episode of season j. Kyle's viewing of the show's episodes can be summarized by the following pseudocode. WATCHSERIES(titles ...n, 1..131): For each i l ton For each j = 1 to i For each k l to 13 Watch episode titles[j, k]. Find a new show to watch. (b) Give a tight asymptotic bound for the total amount of time Kyle spends watching "Parks and Office Places" according to the above pseudocode. Your bound should be given as (g(n)) for some simple function g(n), and you should briefly justify your answer. (Hint: The numbers 20 and 13 are both constants.) (c) "Parks and Office Places" has already been renewed for its 10th season, and Kyle cannot afford to spend all of his time rewatching every episode as explained above. Give a tight asymptotic bound for the total amount of time Kyle will spend watching "Parks and Office Places" if he only rewatches episodes of one previous season every time a new season comes out. Again, briefly justify your answer. The last part of this question has nothing to do with television. (d) Sort the functions of n listed below from asymptotically smallest to asymptotically largest, indicating ties if there are any. Do not turn in proofs for this prob- lem. (But you may want to write the proofs for yourself any way so you know if you're correct.) To simplify your answers, write f(n) gn) to mean f(n) = o(g(n)), write f(n) = g(n) to mean f(n) = (g(n)), and list all the functions in a sequence of these inequalities. For example, if the given functions were n?, n, (), and n then the two correct answers would be "n<n? = ) <n" and "n< 0) = n< 3 3 6" 23 nan lon lin lg 3n 300 logon n + 1000 100.5 Vn 2-sinn n log n (Hint: You should be able to solve this problem using only what is written in the lecture notes on asymptotic analysis along with basic algebraic rules for manipulating logs, polynomials, and exponentials.

Answer 1

for each kol to 13. Walth resort lilla liik] eech cpuede = 20 min total crisedel in coch seaton 5 Total time token to watch all realone Crestrooon) ty perrront) hart se and thord) 1 (20713) + 2. (2013.) + 3. (2013) 12 . 7 (2013) = (26x13) (1+ 2+ 3+ na - nenti & (20813) " - 130x n(n+12 upper bound. olibourh+12) ang = non rutig coche) o Kylie only watches the previous season 1. (20x13) +2./20x13) + 2 (20113 + 2.120x13) + (20x13) [1 + 2Cht) This is a tight bound 0|(20813) (1+264-1)) on

Date Page No. 3 » m' > loom >> m= 119 an+1000 >> 29 > logen » legm az lcg3n » 55 s lcgrzan » 2-sinn » 300