(a) Below is the pseudo-code for two algorithms: Practicel (A,s,f) and Practice2(A,s,f), which take as input...

Transcribed Image Text:

(a) Below is the pseudo-code for two algorithms: Practicel (A,s,f) and Practice2(A,s,f), which take as input a sorted array A, indexed from s to f. The algorithms make a call to Bsearch(A,s,f,k) which we saw in class. Determine the worst-case runtime recurrence for each algorithm: T₁(n) and T₂(n). Show that Ti (n) is O(log n) and T₂(n) is O(n logn). Practicel (A,s,f) if s < f else q1 = [(8 + f)/2] if BSearch(A,s,q1,1) = true return true else return Practice l(A, q1+1, f) return false Practice 2 (A,s,f) if s < f else if BSearch(A,s+1,f,1) = true return true else return Practice2(A, s, f-1) return false (a) Below is the pseudo-code for two algorithms: Practicel (A,s,f) and Practice2(A,s,f), which take as input a sorted array A, indexed from s to f. The algorithms make a call to Bsearch(A,s,f,k) which we saw in class. Determine the worst-case runtime recurrence for each algorithm: T₁(n) and T₂(n). Show that Ti (n) is O(log n) and T₂(n) is O(n logn). Practicel (A,s,f) if s < f else q1 = [(8 + f)/2] if BSearch(A,s,q1,1) = true return true else return Practice l(A, q1+1, f) return false Practice 2 (A,s,f) if s < f else if BSearch(A,s+1,f,1) = true return true else return Practice2(A, s, f-1) return false

Answer rating: 100% (QA)

Answer 1 Since T 1 when h2kTn T 1 K Log n 0 0 Logn 2 T2 n0 n Lo... View the full answer