reset password
Author Message
skim144
Posts: 63
Posted 12:56 Oct 08, 2014 |

Can anyone explain again why the # of operations taken in merging part was 'An + B' ?

I'm trying to understand but I can't

This was from 2nd quiz last Thursday(10/2).

G190852562
Posts: 162
Posted 22:38 Oct 08, 2014 |

First off, an operation is typically any comparison or assignment.

So something like

if(1 < 2)
x = 3;

would run in 2 operations.  (Chances are the compiler would actually see that the comparison is always true and execute the code block without doing the comparison, so in only 1 operation).  With me so far?  Good.

Next we will look at the merge part of merge sort(merge sort just calls merge a lot of times).  What merge does is it takes 2 sorted arrays and spits out 1 sorted array.  Let's take a look at how this works.

Let's say we're merging [1, 4, 5] with [2, 3, 6].  Both arrays are sorted, and now  we need to merge them.  Let's try sticking one to the end of the other: [1, 4, 5, 2, 3, 6].  Nope not 1 big sorted array.  Interweaving the two arrays(like bridging a deck of cards) is no good: [1, 2, 4, 3, 5, 6].  What we need to do is start by comparing the first elements in both arrays.  So 1 is the smallest.
[_, 4, 5] [2, 3, 6] [1, _, _, _, _, _].  Next we compare the first elements again [_, 4, 5] [_, 3, 6] [1, 2, _, _, _, _] and again until we have a sorted array [1, 2, 3, 4, 5, 6].

So now that we know what merge sort should do, the pseudo-code should look like

for k = 1 to n
    if A(i) < B(j)
        C(k) = A(i++)
    else if A(i) > B(j)
        C(k) = B(j++)

verify that is the algorithm you were using when merging the two arrays from earlier.

Now we start counting the number of operations.  Each iteration, you are doing a comparison, an assignment, and then incrementing (either i or j).  So you have to execute 3 operations each iteration.  And how many iterations(loops) are there?  Well this is fairly obvious for a for loop, it loops N times, the size of the array.  So the running time for a merge is 3*N.

But wait, what about when you increment k, when you perform the test condition before entering an iteration
for(int i = 0; i < N; i++) and other stuff?  It does not execute exactly 3 or 4 operations each loop, but you should recognize that it performs a CONSTANT number of operations per loop, we'll call it A.  We are going to be missing a few other operations too like initializing i to 0, so we collect the other constants we miss as B.

A*N + B

skim144
Posts: 63
Posted 14:25 Oct 13, 2014 |

Beautiful explanation. Thank you so much!