Suppose we run ternary search on a very large array of n ele

Suppose we run ternary search on a very large array of n elements In Big O notation, what is the best upper bound for the worst-case asymptotic time complexity of ternary search? In other words, in the worst case, the running time of ternary search is O of what? Is this asymptotically better, worse, or the same as binary search on an array of the same size? Briefly justify your answer We talked about how binary search compares a number to be searched with the middle element of a sorted array, successively searching the right half of the array if the number is greater than the middle element or the left half of the array if the number is less than the middle element. This is performed until the number has been found or (in the worst case) until the half of the array to be searched contains no elements (at which point we conclude that the number is not in the array). We also discussed how this algorithm is O(log_2 n) because as the array size (n) doubles, the number of comparisons needed increases by 1. Now consider ternary search, which compares a number to be searched with the elements that are a third of the way from the ends of a sorted array. Essentially, this algorithm breaks the sorted array into three parts and chooses to continue searching in the one that the number to be searched would have to fall into. For example, suppose we have the sorted array array = {1, 4, 6, 9, 10, 11, 14, 20, 25, 33, 38} and we are looking for the number 15. The \"breakpoints\" of the array are at array [3], which is 9, and array [7], which is 20. Since 15 is between 9 and 20, we look at the middle third of the array, which contains 10, 11, and 14. Again, we continue searching just one third of each successive array until we find the number or reach an array with no elements.

Solution

I don\'t know what\'s your question .As there is no question posted but just the explanation of two searches.So, I will write answer over which among these 2 searches preferred.

So,
From the first look of these explanation or if we look at the code,it looks that the ternary search does less no. of comparisons as it makes Log₃n and whereas binary search makes Log₂n .But,lets us take a closer look.

In the worst case scenario,
The binary search\'s recursive formula :

T(n) = T(n/2) + 2; T(1) = 1

The ternary search\'s recursive formula:

T(n) = T(n/3) + 4 ; T(1) = 1

So , for worst case scenario ; binary search takes comparisons 2Log₂n + 1 and whereas ternary search takes comparisons 4Log₃n + 1. Therefore, when we compare the no. of comparisons of Ternary and Binary Searches boils down the comparison of expressions 2Log3n and Log2n . The value of 2Log3n can be written as (2 / Log23) * Log2n . Since the value of (2 / Log23) is more than one, Ternary Search does more comparisons than Binary Search in worst case.

So,therefore Binary search is preferred over ternary search