CODEWITHSUNDEEP
algorithm
amitabha
amitabha

Reputation: 646

Merge sort comparison

I am reading "Analysis of Algorithms" by Sedgewick and Flajolet.In page 7 theoren 1.1 gives:

enter image description here

And the proof is given below:enter image description here

Can some one explain this where O(N) goes?Because it proves Cn is O(NlogN).

Upvotes: 2

Views: 257

Answers (2)

Gene
Gene

Reputation: 46990

I'm not sure exactly where the O(N) you're asking about is wrong or missing, but their analysis is fine for the special case N = 2^n.

The first line of math after (1) just re-states the recurrence for the special case. The next, long line of math shows

C_{2^n} = (2^n) n

Now we know 2^n = N and so n = lg N. Substituting with both of these we get

C_N = N lg N

as they say. If I'm not seeing your question correctly, please comment.

Upvotes: 0

David Eisenstat
David Eisenstat

Reputation: 65498

You're right; for reasons that are beyond me, they stated more theorem than they actually proved. Here's one way to fill in the rest.

Lemma Let T(n) for integers n >= 1 be defined by

T(n) = 0,                                for n = 1;
       T(floor(n/2)) + T(ceil(n/2)) + n, for n > 1.

Then T(n) <= n lg n + n - 1 = n lg n + O(n) for integers n >= 1.

Proof By induction. For n = 1, T(1) = 0 = 1 lg 1 + 1 - 1. For n > 1, there are two cases. If n is even, then

T(n)  = 2T(n/2) + n
     <= 2(n/2) lg(n/2) + 2n/2 - 2 + n
      = n (lg n - 1) + 2n - 2
     <  n lg n + n - 1.

If n is odd, then things get complicated.

T(n)  = T(n/2 - 1/2) + T(n/2 + 1/2) + n
     <=   (n/2 - 1/2) lg(n/2 - 1/2) + (n/2 - 1/2) - 1
        + (n/2 + 1/2) lg(n/2 + 1/2) + (n/2 + 1/2) - 1
        + n
      = (n/2 - 1/2) lg(n/2 - 1/2) + (n/2 + 1/2) lg(n/2 + 1/2) + 2n - 2.

The two ugly terms both are close to (n/2) lg(n/2), so we write each as that quantity plus an error term.

T(n) <= (n/2 - 1/2) lg(n/2 - 1/2) + (n/2 + 1/2) lg(n/2 + 1/2) + 2n - 2
      =   (n/2) lg(n/2) + ((n/2 - 1/2) lg(n/2 - 1/2) - (n/2) lg(n/2))
        + (n/2) lg(n/2) + ((n/2 + 1/2) lg(n/2 + 1/2) - (n/2) lg(n/2))
        + 2n - 2
      =   n lg(n/2) + 2n - 2
        + (n/2 - 1/2) lg(n/2 - 1/2) - (n/2) lg(n/2)
        + (n/2 + 1/2) lg(n/2 + 1/2) - (n/2) lg(n/2)
      =   n (lg n - 1) + 2n - 2
        + (n/2) (lg(n/2 - 1/2) - lg(n/2)) - (1/2) lg(n/2 - 1/2)
        + (n/2) (lg(n/2 + 1/2) - lg(n/2)) + (1/2) lg(n/2 + 1/2)
      =   n lg n + n - 2
        + (n/2) lg((n/2 - 1/2)/(n/2)) - (1/2) lg(n/2 - 1/2)
        + (n/2) lg((n/2 + 1/2)/(n/2)) + (1/2) lg(n/2 + 1/2)
      =   n lg n + n - 2
        + (n/2) lg(1 - 1/n) - (1/2) lg(n/2 - 1/2)
        + (n/2) lg(1 + 1/n) + (1/2) lg(n/2 + 1/2)
      =   n lg n + n - 2
        + (n/2) lg(1 - 1/n) + (n/2) lg(1 + 1/n)
        + (1/2) lg(n/2 + 1/2) - (1/2) lg(n/2 - 1/2)
      =   n lg n + n - 2
        + (n/2) lg((1 - 1/n) (1 + 1/n))
        + (1/2) lg((n/2 + 1/2) / (n/2 - 1/2))
      =   n lg n + n - 2
        + (n/2) lg(1 - 1/n^2)
        + (1/2) lg(1 + 2/(n - 1)).

The term (n/2) lg(1 - 1/n^2) is negative, and, for n >= 3, the minimum n for this case, the term (1/2) lg(1 + 2/(n - 1)) is at most 1/2. (Actually, we could go back and redo the proof to show that T(n) <= n lg n + n/2 - 1/2. I'm going to leave that as an exercise.) Hence,

T(n) <    n lg n + n - 2
        + 0
        + 1
      = n lg n + n - 1.

Upvotes: 3

Related Questions