Question

Describe how the number of comparisons used in the worst case changes when these algorithms are used to search for an element of a list when the size of the list doubles from n to 2n, where n is a positive integer.

a) Linear search
b) Binary search

Answer 1

The linear search changes from O(1) to O(n), and binary search changes from O(1) to O(log n). Where n is an integer.

Step-by-step explanation:

The linear algorithm transverse through a list of items until the target value is found. When a search is conducted, the algorithm moves through the unordered list, one item at a time, denoted as O(1). But when the list size is increased, it is gets to the worse case of O(n) with n as the integer of the increased value.