Question

Write an algorithm that searches a sorted list of \(n\) items by dividing it into three sublists of almost \(n / 3\) items. This algorithm finds the sublist that might contain the given item and divides it into three smaller sublists of almost equal size. The algorithm repeats this process until it finds the item or concludes that the item is not in the list. Analyze your algorithm and give the results using order notation.

Short answer

The ternary search algorithm works by dividing the sorted list into three equal parts and then determining in which part the item might exist. The process is then repeated for that part. The time complexity of a ternary search algorithm comes out to be \(O(log3 n)\).

Step-by-step solution

Understanding Ternary Search

In a ternary search, the list is divided into three equal parts. We initially compare the given item with the middle two items of the list. We disregard the sublists where the item cannot be present and continue searching in the remaining sublist.

Writing the Algorithm for Ternary Search

Algorithm:\begin{enumerate} \item If the list is empty, return the list does not contain the item. \item Calculate two midpoints, say \(mid1\) and \(mid2\), which will divide the given list into three equal parts. \item If \(item == list[mid1]\), return \(mid1\). \item If \(item == list[mid2]\), return \(mid2\). \item If \(item < list[mid1]\), then continue the search in the left section of the list. \item If \(item > list[mid2]\), then continue the search in the right section of the list. \item If \(list[mid1] < item < list[mid2]\), then continue the search in the middle section. \item Continue the same steps recursively until finding the element or till the list is empty.\end{enumerate}

Time complexity analysis of Ternary Search

The time complexity of ternary search can be defined based on the number of recursive calls performed during the search operation. In each recursive call, we divide the list into three sublists, hence reducing the size to one-third of the current size. So, we can write it as T(n) = T(n/3) + O(1), which simplifies to O(log3 n) using the master theorem.

Key concepts

Divide and Conquer Technique

The Divide and Conquer technique is a foundational strategy for solving complex problems by breaking them down into more manageable sub-problems. This method consists of three main steps: divide, conquer, and combine. In the context of the ternary search algorithm, the list of items is divided into three equally-sized sublists during the 'divide' step.

Next, the 'conquer' step involves determining which of these sublists contains the key item. If the key item is not equal to the middle elements, one of the three sublists can be chosen to continue the search based on where the key item can potentially be found, effectively reducing the problem's size. Lastly, the 'combine' step would simply be the aggregation of the results, but in the case of ternary search, there's no explicit combining as we're simply searching for an item.

Time Complexity Analysis

Time Complexity Analysis is crucial to understanding how the runtime of an algorithm scales with the input size. With the ternary search algorithm, each recursive step divides the list into three, which significantly reduces the search area.

The time complexity expresses how many iterations the algorithm must make to find the item or conclude its absence. As the solution mentions, every recursive call to the ternary search handles one third of the previous list's size. This pattern can be mathematically expressed through a recurrence relation which leads us to understand that the time complexity of the ternary search is logarithmic, specifically in the base of three, noted as O(log3 n). This is because it takes a logarithmic number of steps (divisions of the list) to reduce the search area to just one element.

Order Notation

Order Notation, often referred to as Big O notation, is a mathematical concept used to describe the upper bound of an algorithm's run time or space requirements in the worst-case scenario. When we describe the ternary search algorithm as having a time complexity of O(log3 n), we are proclaiming that the maximum number of operations needed grows logarithmically with the number of items.

This notation provides a high-level understanding of how the algorithm will perform as the size of the input increases, allowing for the comparison of efficiency between different algorithms. It's important to note that constants and smaller-order terms are omitted in Big O notation because they don’t significantly affect the growth rate as the input size becomes very large.

Recursive Algorithm

A Recursive Algorithm is one that solves a problem by solving smaller instances of the same problem, except for base cases which are solved directly. The ternary search algorithm is a perfect example of recursion since it calls itself with a smaller sublist until it meets the condition that the item has been found or the sublist is empty.

This self-referential approach enables a clear and concise implementation of the divide and conquer strategy. A recursive algorithm typically consists of base cases that terminate the recursion and a recursive step where the algorithm calls itself with modified parameters. When writing a recursive algorithm like ternary search, it's vital to ensure that the base cases cover all possible situations where recursion should not continue to prevent infinite loops.