(a1, a2,..., Consider the following recursive algorithm, which takes as input a sequence , an) of...

     

Transcribed Image Text:

(a1, a2,..., Consider the following recursive algorithm, which takes as input a sequence , an) of n numbers, where n is a power of two, i.e., n = 2k for some integer k > 0: Algorithm MYSTERY (a1, a2,..., an): if n = 1 then return ai else for i = 1 to n/2 endif do b₁ = min(a2i-1, a2i) endfor; MYSTERY (b1, b2, ..., bn/2) (*) ⚫ Determine the output of algorithm MYSTERY (a1, a2,..., an). As always, justify your answer. For any integer n ≥ 1 that is a power of two, let T(n) be the number of times that line (*) is executed when running algorithm MYSTERY (a1, a2,..., an). Derive a recurrence for T(n) and use it to prove that for any integer n ≥ 1 that is a power of two, T(n) = n 1. Activate V Go to Setting (a1, a2,..., Consider the following recursive algorithm, which takes as input a sequence , an) of n numbers, where n is a power of two, i.e., n = 2k for some integer k > 0: Algorithm MYSTERY (a1, a2,..., an): if n = 1 then return ai else for i = 1 to n/2 endif do b₁ = min(a2i-1, a2i) endfor; MYSTERY (b1, b2, ..., bn/2) (*) ⚫ Determine the output of algorithm MYSTERY (a1, a2,..., an). As always, justify your answer. For any integer n ≥ 1 that is a power of two, let T(n) be the number of times that line (*) is executed when running algorithm MYSTERY (a1, a2,..., an). Derive a recurrence for T(n) and use it to prove that for any integer n ≥ 1 that is a power of two, T(n) = n 1. Activate V Go to Setting

Answer rating: 100% (QA)

To determine the output of the MYSTERY algorithm when given input a sequence a1 a2an of n numbers wh... View the full answer