Package topics.divideconquer

package topics.divideconquer

Divide-and-Conquer algorithms — break, solve, and combine.

Divide and Conquer solves problems by recursively splitting them into smaller sub-problems of the same type, solving each sub-problem independently, and then merging the partial results into a final answer.

Recurrence and the Master Theorem

The running time of a divide-and-conquer algorithm typically satisfies:

T(n) = a · T(n/b) + f(n)

where a is the number of sub-problems, b is the size reduction factor, and f(n) is the cost of dividing / combining.

Distinction from Dynamic Programming

• Divide & Conquer — sub-problems are independent; solved once.
• Dynamic Programming — sub-problems overlap; results are cached.

Classes in This Package

• BinarySearch — O(log n) search in sorted arrays
• Factorial — recursive factorial
• Fibonacci — recursive Fibonacci
• GCG — greatest common divisor (Euclidean)
• MajoritarianElement — majority element by D&C
• MaxSum — maximum subarray sum
• Median — median of two sorted arrays
• Mergesort — O(n log n) stable sort
• Mode — mode by D&C
• SequentialSearch — linear search baseline
• VectorSum — parallel vector sum

Related Packages

Package	Description
topics.divideconquer.utils	Utility classes shared by divide-and-conquer implementations.

Classes

Class	Description
BinarySearch	Binary Search implementation for finding an element in a sorted array.
Factorial	DIVIDE AND CONQUER PROBLEM: CALCULATE THE FACTORIAL OF A NUMBER
Fibonacci	Fibonacci Number Calculation using Divide and Conquer and Iterative Approaches.
GCG	GREATEST COMMON DIVISORS: Calculate the GCG of two positive integers
MajoritarianElement	//DIVIDE AND CONQUER PROBLEM: IS THERE A MAJORITARIAN ELEMENT IN n ELEMENTS?
MaxSum	DIVIDE AND CONQUER PROBLEM: MAXIMUM SUMMATION OF ALL THE SUBSEQUENCES OF n ELEMENTS
Median	//DIVIDE AND CONQUER PROBLEM: THE MEDIAN OF n ELEMENTS
Mergesort	Mergesort algorithm using divide-and-conquer.
Mode	//DIVIDE AND CONQUER PROBLEM: MODE OF n ELEMENTS
SequentialSearch	DIVIDE AND CONQUER PROBLEM: CALCULATE THE POSITION OF AN ELEMENT x IN A VECTOR (SORTED OR UNSORTED) OF n DIFFERENT ELEMENTS
VectorSum	DIVIDE AND CONQUER PROBLEM: CALCULATE THE SUM OF n ELEMENTS IN A VECTOR