You\'ve asked a colleague to write a fast search method to determine whether a s

Question

You've asked a colleague to write a fast search method to determine whether a string occurs in a given set of strings. You've told the colleague that the set could be large, and that the method should run efficiently. He's come up with a technique he calls Septenary Search. His method assumes that the input consists of a list L of strings (in sorted order) and a given string s. His method works by calling a HELPER function which is recursive. The pseudocode for Septenary Search and HELPER is given below. septenarysearch(L, s) : HELPER(L, 0, L.length-1, s) HELPER(L, Lo, Hi, s) : if Hi - Lo + 1 > 7 : basic_group_size = floor(Hi - Lo + 1) / 7) number_of_larger_groups = (Hi - Lo + 1) % 7 for i in 0..6: group_size = basic_group_size if i

Explanation / Answer

Yes the complexity is O(log n) as the there is one loop and some other statements , the loop is bifircated in polynomial of log n to base 2.

O (1) + O(log n) +O(1) = O (log n)

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

---

---

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