Recitation 1: Asymptotic Complexity, Peak Finding

TL;DR

The 1D peak finding algorithm has a running time of θ(log n), while the 2D peak finding algorithm has a running time of θ(m log n).

Transcript

The following content is provided under a Creative Commons license. Your support will help MIT OpenCourseWare continue to offer high quality educational resources for free. To make a donation or view additional materials from hundreds of MIT courses, visit MIT OpenCourseWare at ocw.mit.edu. VICTOR COSTAN: Hi, everyone. I am Victor. My full name is ... Read More

Key Insights

• 🙊 Both the 1D and 2D peak finding algorithms employ divide and conquer techniques to search for local peaks efficiently.
• 🙊 The 1D peak finding algorithm has a time complexity of θ(log n) and the 2D peak finding algorithm has a time complexity of θ(m log n).

Questions & Answers

Q: What is the running time of the 1D peak finding algorithm?

The running time of the 1D peak finding algorithm is θ(log n) in the worst case. It starts in the middle and systematically searches for a local peak by comparing neighboring elements and deciding the next move based on the comparison.

Q: How does the 2D peak finding algorithm work?

The 2D peak finding algorithm finds a local peak in a 2D matrix. It first finds the maximum value in a column, checks neighbors to determine if it's a peak, and recurses to the right or left side of the matrix based on the comparison. The recursion continues until reaching a base case of a single column, where the maximum value is guaranteed to be a peak.

Q: What is the running time of the 2D peak finding algorithm?

The running time of the 2D peak finding algorithm is θ(m log n) in the worst case. It starts by finding the maximum value in a column, which takes θ(m) time. Then, it divides the problem in half and recursively applies the algorithm on one side. The recursion continues until reaching the base case of a single column. The overall time complexity is determined by the number of divisions, which is log n.

Q: What is the advantage of using the 1D peak finding algorithm instead of the maximum value method in the 2D peak finding algorithm?

The advantage of the 1D peak finding algorithm is its faster running time compared to the maximum value method in the 2D peak finding algorithm. The 1D peak finding algorithm has a time complexity of θ(log n), while the maximum value method has a time complexity of θ(m log n). This means that the 1D peak finding algorithm can potentially be significantly faster for large input sizes, especially when m and n are both large.

Summary & Key Takeaways

• 1D peak finding: The algorithm searches for a local peak in a 1D array by starting in the middle, checking neighbors, and deciding which direction to move based on the comparison with the neighbors. This has a running time of θ(log n).

• 2D peak finding: The algorithm searches for a local peak in a 2D matrix by finding the maximum value in a column, checking neighbors, and recursively dividing the problem until reaching a base case of a single column. This has a running time of θ(m log n).