University CS 320: Design and Analysis of Algorithms Homework 2

This document presents solutions to a homework assignment focused on the design and analysis of algorithms. The first part of the solution addresses finding the recurrence relation for a given equation, specifically calculating the value of T(625) using the provided formula and breaking down the steps to arrive at the answer. The second part of the solution provides a non-recursive algorithm for merge sort, explaining the concept of inversions and how to count them during the merge step. The solution includes a detailed explanation of the MergeAndCount function, which produces a sorted list and counts cross inversions, and the SortAndCount function, along with its recurrence relation and time complexity analysis using the master theorem, concluding that the algorithm's running time is O(n log n).