Give a bigOh estimate for the number of comparisons for the

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)

Solution

Solution:

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

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(n²).