Question

We would say that Binary Search: a. Runs in O(lg(n)) time because it will cut the list size in half for each iteration. b. Runs in O(n2 ) time, because for each element in the list we have to scan the rest of the list to ensure there are no duplicates. c. Runs in O(n) time since it has to scan the entire list. n is the length of the list, so it is the total runtime.

Answer 1

Answer:

The answer is "Option c".

Explanation:

A analyze the process which finds the location of the desired value within the same given list is also called a quarter, linear interpolation search.

• Suppose the length of the array is = n

• Search space is cut in half at every iterator, so array at the first iterative process is= 2
• Size in second iteration is = 22
• In the third iteration size = u 25
• In Kth point iteration the size is = n2k  
• divide the value by k the length of the array will be 1.

   $=> \frac{n}{2k} = 1\\ \\=> n= 2k \\\\\ Taking \ \log \ both \ side \\\\=> log n = log 2k \\\\=> log2 (n) = k log \frac{2}{2} \\\\=> k = log2 (n) \ \ \ \ \ \ \ \sin log \frac{2}{2} = 1 \\\\=> O(lg(n))$