3. Analyze the worst-case time complexity of the algorithm below. Input: n: nonnegative integer 1 Algorithm:...

   

Transcribed Image Text:

3. Analyze the worst-case time complexity of the algorithm below. Input: n: nonnegative integer 1 Algorithm: LoopMystery 2 sum = 0 3 t = 1 4 d=1 5 k = n 6 while k> 1 do 7 for 1 to k do t=t+d sumsum + t if k is odd then 8 9 10 end 11 12 | d= -d 13 end k = [k/2] 14 15 end 16 return sum 3. Analyze the worst-case time complexity of the algorithm below. Input: n: nonnegative integer 1 Algorithm: LoopMystery 2 sum = 0 3 t = 1 4 d=1 5 k = n 6 while k> 1 do 7 for 1 to k do t=t+d sumsum + t if k is odd then 8 9 10 end 11 12 | d= -d 13 end k = [k/2] 14 15 end 16 return sum