0

Hi,
i understand merge sort & quick sort even i can write the programs but iam unable to understand its complexity.

its very easy to derive complexity equations for selection & bubble sort.

as the code is little complex & recursive nature i am unable to understand its complexity and how its n log n.


please some one provide me some easy method to understand its complexity.

considering 16 elements in the list.

selection & bubble it takes O(n2);

but quick and merge 16 * 4 = 64.

2
Contributors
1
Reply
6
Views
7 Years
Discussion Span
Last Post by Narue
1

All you're doing with the divide and conquer is breaking up the list into smaller lists, then putting the sorted smaller lists back together. This breakdown and rebuilding is an O(logn) operation:

0 1 2 3 4 5 6 7 8 9 A B C D E F
0 1 2 3 4 5 6 7
0 1 2 3
0 1
    2 3
0 1 2 3
        4 5 6 7
        4 5
            6 7
        4 5 6 7
0 1 2 3 4 5 6 7
                8 9 A B C D E F
                8 9 A B
                8 9
                    A B
                8 9 A B
                        C D E F
                        C D
                            E F
                        C D E F
                8 9 A B C D E F
0 1 2 3 4 5 6 7 8 9 A B C D E F

Now add to that the O(n) cost of sorting each partial list, and you've got the classic O(n * logn) complexity.

This question has already been answered. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.