401 HW 2

Homework 2

Mateo Viteri - mvite4

Christian Penaloza - cpena29

Anthony Valenzo - avale34

\today

Binary Search

(a) Including the initial one, how many total calls will be made for BinarySearch(A, 1, 10, 13)?

4 calls

(b) Including the initial one, how many total calls will be made for BinarySearch(A, 1, 10, 0)?

3 calls

(c) Including the initial one, how many total calls will be made for BinarySearch(A, 1, 10, 3)?

5 calls

Intersecting Lines

(a) The algorithm would store pairs into tuples, sort them by their first element (bottom points), and then get the list of second elements (top points) with the new order. Then we use the merge-sort algorithm shown in class to count inversions and return that number of inversions.

(b) Let pairs be an empty list of pairs.

For each corresponding pair (p,q) in P and Q:

    Add (p,q) to pairs.

Sort pairs in ascending order by their first element using a Θ*(n*(log_)(n)) algorithm.

Let top_points be an empty list.

For each (p,q) in pairs:

    Add q to top_points, maintaining the original order.

sorted_top_points,intersections←Inversions(top_points).

Return intersections.

(c) An intersection occurs when (p_i)<(p_j) and (q_i)>(q_j), the latter being an inversion. So, we sort the pairs in ascending order by p, ensuring (p_i)<(p_j). Then, we count the number of inversions in the list of q's with the new order, which is the same as counting the number of (q_i)>(q_j). When sorting, we move both points p and q together so that we don't lose the original order. Thus, counting inversions correctly gives the number of intersections.

(d) Both for loops take Θ(n), and we specifically mentioned to use an Θ*(n*(log_)(n)) sorting algorithm to sort pairs. The Inversions algorithm shown in class runs in Θ*(n*(log_)(n)) time. Thus, the overall time compelxity is Θ*(n*(log_)(n)).

T(n)=2*T*(n/2)+Θ(n)

Since a=2,b=2,c=1 and k=0 we get Θ*(n*(log_)(n)).

Playing Hooky

(a) Write your answer for Question 3, part (a) here.

(b) Write your answer for Question 3, part (b) here.

(c) Write your answer for Question 3, part (c) here.

References

“Divide and Conquer - Inversion Count.” YouTube, uploaded by Neso Academy, 22 June 2021, https://www.youtube.com/watch?v=7_AJfusC6UQ. Accessed 20 Sept. 2026.

“Gemini.” Google, Sept. 2026 version, https://gemini.google.com. Accessed Sept. 2026. Used for grammar and Latex formatting.