1: function SUMELEMENT array A 2: if length(A)1: 3: return ?? 4: else: 6: 7: 8:

Question

1: function SUMELEMENT array A 2: if length(A)1: 3: return ?? 4: else: 6: 7: 8: end function Al ? A10 : length(A)/2] A2Allength(A)/2 length(A)] return SumElement(A1) + 2* SumElement(A2) Assume that items in the first half of array A are copied into array A1 and the items in the second half of array A are copied into array A2 (i.e. these are O(n) operations) 1. Write the running time of this function as a recurrence relation. 2. Using Master Method give the running time complexity of this function in Big O notation

Explanation / Answer

if lenght(A)==1

return A[0] ; T(1)

else

A1=A[0:lenght(A)/2]   

A1=A[lenght(A)/2 : length(A) ] O(n)

return sumelement(A1)+2*sumelement(A2) T(n/2)+2*T(n/2)

running time this function :

T(n)=T(1)+O(n)+T(n/2)+2*T(n/2)

T(n)=3T(n/2)+O(n)

MASTER THEOREM APPLY FOR TEH RECURRENCE OF THE FOLLWOING FORM

T(n)=aT(n/b)+f(n)

where a>=1 and b>1 are constant and f(n) is asymptotically positive function.

There are following three cases:

1. If f(n) = ?(nc) where c < Logba then T(n) = ?(nLogba)

2. If f(n) = ?(nc) where c = Logba then T(n) = ?(ncLog n)

3.If f(n) = ?(nc) where c > Logba then T(n) = ?(f(n))

here T(n)=3T(n/2)+O(n)

a=3, b=2,c=1

lob23=1.58

c<log23 => 1<1.58

so according to master theorem condition 1

running time complexity of this function T(n)=O(nlog23)

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

---

---

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