Chapter 3: Searching Techniques

What are the three types of analysis in algorithm performance?

Best-case, average-case, and worst-case analysis.

What does Big-O analysis measure?

It measures the upper bound of an algorithm's time complexity.

What is the key operation to characterize performance in searching algorithms?

Counting the number of comparisons made when searching for a value.

How does the size of the problem affect performance analysis?

Performance is analyzed as the size of the problem grows, often represented by the number of comparisons for an array of size N.

What is time complexity?

Time complexity is the time taken by a computer to run an algorithm.

What is space complexity?

Space complexity is the amount of memory required by a computer to run an algorithm.

What external factors can affect algorithm complexity?

The size of the input, speed of the computer, and quality of the compiler.

What does O-notation represent in asymptotic notation?

O-notation represents the upper bounds of an algorithm's growth rate.

What does Ω-notation represent in asymptotic notation?

Ω-notation represents the lower bounds of an algorithm's growth rate.

What does Θ-notation represent in asymptotic notation?

Θ-notation represents tight bounds, where the growth rates of two functions are equal.

What are the primary types of searching algorithms?

Sequential search and binary search.

What is the basic operation in sequential search?

Comparison.

What is the best-case complexity of linear search?

O(1), when the element is found in the first position.

What is the worst-case complexity of linear search?

O(n), when the element is at the last position or not found.

What is the average-case complexity of linear search?

O(n), when the element is in the middle of the array.

What is the basic operation in binary search?

Comparison of the middle element with the key.

How does binary search determine which half of the array to search next?

It compares the key with the middle element and chooses the left or right half based on whether the key is smaller or larger.

What is the maximum number of comparisons in a binary search for an array of size 32?

At most 6 comparisons, as it follows a logarithmic pattern.

How does the efficiency of binary search compare to sequential search as n grows large?

Binary search is much more efficient, with a running time of θ(log(n)) compared to θ(n) for sequential search.

What is the sequential search algorithm's approach to finding an element?

It checks each element in the array sequentially until it finds a match or reaches the end.

What happens if the element is not found in a linear search?

It returns a NULL value.

What is the output of a binary search if the key is found?

The location (index) of the key in the sorted array.

What is the output of a binary search if the key is not found?

The location is set to 0.

What is the significance of the 'floor' function in the binary search algorithm?

It ensures that the middle index is an integer when dividing the search space.

What is the role of the condition code in binary search?

It determines which branch of the algorithm to take based on the comparison result.

How does the number of comparisons in sequential search grow with the size of the array?

It grows linearly, with a maximum of n comparisons.

How does the number of comparisons in binary search grow with the size of the array?

It grows logarithmically, specifically log2(n).