Give a big-Oh estimate for the number of comparisons for the following recursive

Question

Give a big-Oh estimate for the number of comparisons for the following recursive algorithm. Assume L contains n elements. Assume we have functions "first-half (L)" and "second-half (L)" which return the appropriate halves of L. E.g. first-half ([1, 2, 3, 4]) = [1, 2] and second-half ([1, 2, 3, 4]) = [3, 4] procedure Find_Interesting(L :list of integers) if (length(L) = 1) return L else for i = 1 to length-of (L) for j = 1 to length-of (L) if (some comparison) then best = first-half(L) else best = last-half(L) return Find_Interesting(best)

Explanation / Answer

Solution:

As the above algorithm have two nested for loops the time complexity for the algorithm will become O(n2).

It is clear that the for loop with i will execute n times. Every time the i loop will exectue, the inner j loop will execute n times. Therefore we get the complexity as O(n*n). This comes upto O(n2).

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

---

---

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