#5 please show work. WIth Ah input ot size n algorithm A requires 1000Vn operati

Question

#5 please show work. WIth Ah input ot size n algorithm A requires 1000Vn operations and algorithm B requires 5n operations. (a) Which algorithm is more efficient in the long run? (b) For which n is algorithm A at least as efficient as algorithm B? (c) For which n is algorithm B at least twice as efficient as algorithm A? . Below is an algorithm for computing a". Input: a number a and a positive integer n) Output: at) :begin :p := 1 -q:= a : i:= n : while i0 do if i is odd then p := p-q : Do the next two steps whether or not i is odd.) q:= q-q i:= i DIV 2 : return p end (a) Show that the algorithm makes O(log2m) passes through the while loop. (b) How many passes does the algorithm make through the loop for n - 3,7 2100 m make through the loop for n = 3, n = 2100 and n 3.2100? 5. Give an example of a relation on S = {2,3,4} wh 5. Give an example of a relation on S [2,3,4) which is not reflexive, not anti-reflexive, not syr hich is not reflexive, not anti-reflexive, not symmetric and not antisymmetric. Explain why your example works. (a) Find 81,$2 and s3. (b) Find a recursive formula for sn. What do you notice? 6. Recursively define ao ai-1 and an-an-1 + 2an-2 for n > 2.

Explanation / Answer

question 6)

Solve the recurrence

an=an1+ 2an2

given the initial conditions a0= 1,a1= 1

an=c1an-1+c2 an-2

c1= 1,c2= 2

– Characteristic equation:

r2r2 = 0

Solutions:

r= [(1)±((1)24·1·(2))1/2] / 2·1

r= 2 orr=1

So an=12n+2(1)n

To find 1and 2

, solve the equations for the initialconditions a0 and a1

a0= 1=a12^0+a2(1)^0

a1= 1 =a121+a2(1)^1

1 =a1+a2

71= 2a1a2

a2=1-a1

1=2a1-(1-a1)

=2a1-1+a1

1=3a1-1

2=3a1

a1=3 and a2=2

an=3.2^2-(-2)^n

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

---

---

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