Consider the following algorithms. SUM2(n, (a_1 a_2, ..., a_n))//n is an integer

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

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.