Member Avatar for Iam3R

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
  • 123 Views
  • 7 Hours Discussion Span
  • Latest Post Latest Post by Narue
Member Avatar for Narue

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.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.