Consider the following algorithms. SUM2(n, (a_1 a_2, ..., a_n))//n is an integer
ID: 3841306 • Letter: C
Question
Consider the following algorithms. SUM2(n, (a_1 a_2, ..., a_n))//n is an integer that in 2 or greater a_1's are doubles x = 0 FOR 1 = 1.0..n - 1 t = 0 FOR j = I + 1 .. n r = a_i * a_j//the asterisk denotes multiplication t = t + r END x = x + t END RETURN x LOG_EST(m) x=m//double count=0//integer WHILE m>l x=x/2 count++ END RETURN count Compute SUM2(3, [6, 7, 8]) and SUM2(4, [1, 2, 3, 4]). Give a general expression for the output in terms of the input values n, a_1, a_2, ..., a_i. Give the worst-case time complexity of SUM2 in terms of n, the length of the input list in O notation. (show work.) Compute LOG_EST(6) and LOG-EST(2). Give a general description of the output. Give the worst-case time complexity of LOG_EST in terms of b. the number of bits it takes to hold the input(use O notation). (Show work.)Explanation / Answer
1.
(3,[6,7,8])
i=1
j=2
r= 6*7=42
t=0+42=42
i=1,j=3
r=6*8=48
t= 42+48=90
x=90
i=2,j=3
r=7*8=56
t=56
x=90+56=146
(4,[1,2,3,4])
i=1
j=2
t=0+2=2
j=3
r=1*3
t=2+3=5
j=4
r=1*4=4
t=4+5=9
x=0+9=9
i=2
j=3
r=2*3=6
t=0+6=6
j=4
r=2*4=8
t=6+8=14
x=9+14=23
i=3
j=4
r=3*4=12
t=0+12=12
x=23+12=35
2. O(n^2)
3.Infinite loop bcoz m is not updated
4.if instead of while(m>1) has it been while (x>1) log(n).
else infinite loop