Scribd
Upload
4 views1 page

Merge Sort Algorithm

The Merge-sort algorithm is a divide-and-conquer method that sorts an array by recursively dividing it into halves, sorting each half, and merging them. The time complexity is analyzed using induction, showing that for an array of size n, Merge Sort takes O(n*log(n)) time. The base case is constant time for arrays of size 1 or 2, and the inductive hypothesis supports the overall complexity result.

Uploaded by

Muhammad Ahsan Shahid
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
4 views1 page

Merge Sort Algorithm

The Merge-sort algorithm is a divide-and-conquer method that sorts an array by recursively dividing it into halves, sorting each half, and merging them. The time complexity is analyzed using induction, showing that for an array of size n, Merge Sort takes O(n*log(n)) time. The base case is constant time for arrays of size 1 or 2, and the inductive hypothesis supports the overall complexity result.

Uploaded by

Muhammad Ahsan Shahid
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Merge-sort Algorithm Time Complexity Using Induction

Merge-sort Algorithm is a divide-and-conquer algorithm that works on:

1. Dividing: Recursively dividing the array into two halves.


2. Conquering: Recursively sorting each half.
3. Combining: Merging the sorted halves into a single sorted array.

Time Complexity Analysis:


Base Case: For an array of size 1 or 2, Merge Sort takes constant time, O (1).
Inductive Hypothesis: Assume that for any array of size k, where k < n, Merge-sort takes O ( k*log(k) )
time.
Inductive Step: Consider an array of size n. Merge Sort divides this array into two halves of size n/2. By
the inductive hypothesis, sorting each half takes O ((n/2)*log(n/2)) time. The merging step takes O(n)
time.

Therefore, the total time for Merge Sort on an array of size n is:

T(n) = 2T (n/2) + O(n)


<= 2c (n/2)*log(n/2) + cn
<= cn*log(n) - cn + cn
<= cn*log(n)

where:

c is a constant.

For any array of size n, Merge Sort takes O(n*log(n)) time.

You might also like