Analyzing Algorithm Complexities: Binary, Linear, Merge Sort & Recurrences

Posted on Dec 15, 2024 in Computers

Algorithm Complexity Analysis

1. Best-Case, Average-Case, and Worst-Case Complexities of Binary Search

Binary search operates on a sorted array. It repeatedly halves the search interval, comparing the target value with the middle element. If the target matches the middle element, its index is returned. Otherwise, the search continues in the left or right half.

Best-case Complexity:

Definition: The minimum time the algorithm takes.

Binary Search Best-case: If the target element is the middle element on the first comparison, the search completes in 1 step.

Time Complexity: O(1).

Average-case Complexity:

Definition: The expected time complexity for all possible positions of the target in the array (or if it doesn’t exist).

Binary Search Average-case: For a sorted array of size n, the algorithm makes approximately log₂(n) comparisons because it halves the problem size in each step.

Time Complexity: O(log n).

Worst-case Complexity:

Definition: The maximum time the algorithm takes.

Binary Search Worst-case: This occurs when the algorithm keeps halving the array until one element remains, and the element is either found or determined to be absent. The total number of steps is ⌊log₂(n)⌋+1, which is proportional to log₂(n).

Time Complexity: O(log n)

2. Linear Search and its Time Complexities

Linear search is a simple algorithm for finding an element in an array or list. It checks each element sequentially from the start until the target is found or the entire array is traversed.

Process:

1. Start from the first element.
2. Compare each element with the target value.
3. If a match is found, return the index.
4. If no match is found by the end, return “not found.”

Time Complexities of Linear Search:

Linear search performance depends on the target’s position (if present) or the number of elements (if absent).

Best-Case Complexity: The target is found in the first position.

Time Complexity: O(1), as only one comparison is needed.

Average-Case Complexity: The target is found somewhere in the middle of the list (on average). On average, the algorithm searches through half the array.

Time Complexity: O(n), where n is the size of the array.

Worst-Case Complexity: The target is not present, or it is the last element in the array. All n elements are checked.

Time Complexity: O(n).

Advantages of Linear Search

• Simple to implement.
• No requirement for sorted data.
• Works for all data types (arrays, linked lists, etc.).

3. Merge Sort: Working and Time Complexities

Merge Sort is a Divide-and-Conquer algorithm used to sort an array or list. It divides the array into smaller subarrays, sorts them, and merges them back to produce the final sorted array.

Working of Merge Sort:

Divide: Recursively split the array into two halves until each subarray contains a single element.

Conquer: Sort each subarray. (Single-element arrays are inherently sorted.)

Merge: Combine the sorted subarrays to form a single sorted array.

Time Complexities of Merge Sort:

Merge Sort has a predictable time complexity due to its structured process of dividing and merging.

Case	Explanation	Time Complexity
Best Case	Occurs when the array is already sorted. The division and merging still occur.	O(n log n)
Average Case	The typical case for random input.	O(n log n)
Worst Case	Occurs for completely unsorted input, but the steps remain the same.	O(n log n)

Space Complexity: O(n) (temporary arrays for merging).

Advantages of Merge Sort:

• Stability: Retains the relative order of equal elements.
• Predictable Performance: Time complexity is O(n log n) for all cases.
• Divide-and-Conquer: Works well with linked lists due to no need for random access.
• External Sorting: Ideal for large datasets that don’t fit in memory because it can sort in parts.

4. Recurrence Relations and Backward Substitution

A recurrence relation is an equation that defines a sequence of values using recursion, where each term is expressed in terms of its previous terms. It is commonly used to describe the time complexity of recursive algorithms.

Example: For a problem of size n, if it is broken into two subproblems of size n/2, and merging results requires n time, the recurrence relation is: T(n) = 2T(n/2) + n

Backward Substitution Method

The backward substitution method is a technique for solving recurrence relations by repeatedly expanding the relation in terms of smaller inputs until a pattern emerges. The pattern is then used to derive a general formula.

Steps for Solving Using Backward Substitution:

1. Start with the Recurrence Relation: Write the given recurrence relation, including the base case.
2. Expand the Relation: Substitute the recurrence relation into itself iteratively for smaller values of n (e.g., n/2, n/4, …).
3. Observe the Pattern: Identify a general expression after a few expansions.
4. Simplify the Expression: Use the base case to terminate the expansion and replace variables (like k) with n.
5. Derive the Closed Form: Combine the observed pattern and base case to obtain the solution.

Advantages of Backward Substitution:

• Intuitive and straightforward.
• Works well for recurrences with clear patterns.
• Helps derive general solutions without requiring advanced techniques.

5. Substitution Method for Solving Recurrence Relations

Steps for Solving Using the Substitution Method:

1. Make an Initial Guess: Assume that the solution is of the form T(n) = f(n), where f(n) is a function of n (e.g., T(n) = O(n²), O(n log n), etc.).
2. Substitute the Guess into the Recurrence Relation: Replace T(n) in the recurrence with the assumed form.
3. Verify the Assumption: Check if the substitution holds for all n by proving it using induction:

• Base Case: Show the solution works for the smallest input size (e.g., n=1).
• Inductive Step: Assume the solution holds for k, and prove it for k+1.

Refine the Guess if Needed: If the guess doesn’t satisfy the recurrence, modify it and repeat the process.

Example: Solve T(n) = 2T(n/2) + n with T(1) = 1

Initial Guess: Assume T(n) = O(n log n). Specifically, guess T(n) = cn log n, where c is a constant.

Substitute the Guess: Substitute T(n) into the recurrence: T(n) = 2T(n/2) + n. Replace T(n/2) with c(n/2)log(n/2): T(n) = 2 * c(n/2)log(n/2) + n. Simplify: T(n) = 2 * c(n/2)[log n – log 2] + n. T(n) = cn log n – cn + n.

Verify the Assumption: Combine terms: T(n) = cn log n – cn + n. Assume T(n) = cn log n holds for some constant c. The additional terms do not affect the dominant term cn log n, so the assumption is valid.

Conclusion: The solution is: T(n) = O(n log n).

Advantages of the Substitution Method:

• Effective for verifying solutions for recurrence relations.
• Provides insights into the dominant terms affecting complexity.
• Useful for proving tight bounds like Θ(f(n)).

---