PLEASE EXPLAIN YOUR CHOICE Complexity (m/choice) * Searches for a value in a sor

Question

PLEASE EXPLAIN YOUR CHOICE

Complexity (m/choice) * Searches for a value in a sorted list. Returns true if * val is contained in the list t, and false otherwise. @pre. t.size) is zero or more * @pre. t is in sorted order *@pre. t has no duplicate elements @param val a value to search for @param t a list *@return true if val is contained in t, and false otherwise public static boolean bsearch (Integer val, Listt) f if (t.size) 0) return false int i-t.size 2; Integer mid-t.get () if (val.equals (mid)) return true return bsearch (val, t.subList (0, i)); return bsearch (val, t.subList(i +1, t.size ))) ) else if (val.compareTo (mid)

Explanation / Answer

1) T(0) = c for some constant positive integer c for base case of T(0), it takes a constant time 2) C. T(n)=T(n/2)+d Every time problem of size n is divided into one subproblem of size n/2 and it takes constant time of d per subproblem

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

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