the merger step in merge sort is linear.
On 4/3/06,
Padmanabhan Natarajan <[EMAIL PROTECTED]> wrote:
This solution looks correct but its still not clear as to how it is linear.
A totally different perspective, can we think of this as a set of points in a plane. Maybe a geometric view of the problem can throw some light.On 4/3/06, Arunachalam < [EMAIL PROTECTED]> wrote:Here is the improvement to my previous algorithm.Observation 1.ax+by can appear in the solution only if ax+bj has appeared in the solution where j > y.Observation 2.ax+bn can be included only if a(x+1)+bn is included in the answer.1. Extract an+bn as the maximum2. Form a heap with a(n-1)+b(n) and a(n)+b(n-1).3. Extract the maximum from the heap ( assume max extracted is ai+bj )4. Add ai+b(j-1) to the heap5. Add a(i-1)+bn also to the heap if the extracted max is ai+bn.So the worst case complexity for this log(n)+log(n-1)+..1.The best case is O(n) where the heap will have only 2 elements.PS: can someone prove using amortized analysis this solution has the complexity of O(n).
On 4/3/06, Mayur <[EMAIL PROTECTED]> wrote:It doesn't matter. It's not correct. :((
Here's what the algo does: -
It was basically an attempted patch to the problem you indicated: -
curMin is the largest number which was not considered for printing at some stage - but might be useful at some
other stage...
Select an + bn
Next select either a(n-1) + bn or an + b(n-1), setting the other one to curMin (or current-minimum).
i.e. Follow the sequence (let arbitrarily a(n-1)+b(n) be larger)
an + bn
a(n-1) + bna(n-2) + bn
...
a(n-k) + bn. <-- at some k, the value of a(n-k) + bn would be smaller than curMin. In this case,
print whatever's there in current-min
Let the pointer 'j' "surge" ahead
Set curMin to be a(n-k) + bn (this number was not printed), and set the surged-ahead flag to B.
Reset the pointer "i" to the last-position again ...
Something like this: --
an + bn, a(n-1)+b(n), a(n-2)+b(n) ... a(n-k)+b(n) ---- a(n) + b(n-1) ------> a(n-1)+b(n-1), a(n-2)+b(n-1), .. a(n-k') + b(n-1)
| or
|____> a(n) + b(n-2), a(n)+b(n-3), ... , a(n)+b(n-m)
| or
|____> a(n-k) + b(n), ...
The whole point is that we must remember only one position for each array (k for A, and m for B). This is the position where it last-broke off its stride.
The algorithm which I wrote doesn't do all this... I mean, my intent was to do this, but the algo's not correct.. I guess I was too eager ...
On 4/3/06, Arunachalam < [EMAIL PROTECTED]> wrote:Hi,It is very hard for me to get the basic flow of this algorithm. Can you explain the basic idea behind the algorithm.regardsArunachalam.
On 4/3/06, Mayur < [EMAIL PROTECTED]> wrote:right... that's correct. Arunachalam's right... Sorry... My second attempt at it...
One assumption, though - the output need not be sorted...
1: curMin <- min( a[0], b[0] ) - 1
2: i <- n, j<-n3: cnt <- 0, whoSurged = NONE;
4: while ( cnt < n )
{
5: output a[i] + b[j]
6: cnt <- cnt + 1
7: if a[i] + b[j] < curMin
8: then if whoSurged == A
9: then j <- j - 1
10: i = n
11: else i <- i - 1
12: j = n
12.5: curMin = min(a[0], b[0]) - 1
13: goto step 4
14: if (a[i-1] + b[j]) < (a[i] + b[j-1])
15: then j <- j - 1
16: if curMin == (min(a[0], b[0]) -1 )
17: then whoSurged = B
18: curMin = a[i-1] + b[j+1]
19: else i <- i - 1
20: if curMin == (min(a[0], b[0]) -1 )
21: then whoSurged = A
22: curMin = a[i+1] + b[j-1]
}
On 4/3/06, iwgmsft < [EMAIL PROTECTED]> wrote:
assume we have set {ai+bj}.. of size n^2
we can solve using MERGE-SORT i think.. to divide this problem into
subproblems will take O(2logn) i.e. O(log n)...
now at the time of merge it will take O(2n) i.e . O(n)... so this time
we can find n largest values(by merging values in decending order)..
correct me if i m wrong..
http"//ww.livejournal.com/users/arunachalam
http"//ww.livejournal.com/users/arunachalam
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
