Groups | Search | Server Info | Keyboard shortcuts | Login | Register

Groups > comp.programming.threads > #1210

Re: About my ParallelSort library

Cross-posted to 2 groups.

Show all headers | View raw

To explain more:

The best case complexity of ParallelSort using mergesort  is:

 ((n/p)* log(n/p)) + O(n/p)

the ((n/p)* log(n/p)) is the complexity of the sorting part.

O(n/p) is the best case complexity of the merging part.

so the best case complexity  is:  ((n/p)* log(n/p))

The worst case complexity of parallel sort library using mergesort is:

 ((n/p)* log(n/p)) +  O(n)

the ((n/p)* log(n/p)) is the complexity of the sorting part.

O(n) is the worst  case complexity of the merging part.

so the worst case complexity is approximatly: O(n)



Amine Moulay Ramdane.


"aminer" <aminer@toto.com> wrote in message 
news:k6sbo2$anb$2@dont-email.me...
>
> Hello all,
>
> I have done some tests with my ParallelSort library and
> i have noticed that it can give up to 3.8x scalability with
> strings, and it give  3x scalability with integers..
>
> The complexity of ParallelSort using mergesort for exemple, is:
>
> ((n/p)* log(n/p)) + O(n/p)
>
>
> And as you know:
>
> If f1 is O(g1) and f2 is O(g2),
> then f1 + f2 is O(max (f1, f2)), where
> max (f1, f2) (x) = max (f1 (x), f2 (x)); for every  x
>
> So the complexity of my Parallel Sort library using mergesort
> is:
>
> (n/p)* log(n/p))  // p is the number of cores.
>
>
> Also i have implemented Parallel MergeSort and Parallel Quicksort,
> but MergeSort is faster and the reccurence equation of the complexity of 
> mergesort is:
>
> T(n) = 2 * T(n/2) + n
>
> cause it take O(n) for the merging part.
>
> It gives:
>
> T(n) = 2 * T(n/2) + n
>
> = 2 (2T(n/4) +n/2) + n
>
> =4T(n/4)+n+n
>
> =4T(n/4)+2*n
>
> =4 (2T(n/8) +n/4) + 2*n
>
> =8T(n/8)+n+2n
>
> =8T(n/8)+3*n
>
> =2k T(n/2^k) + k*n
>
> We want:
>
> n/2k = 1
>
> n = 2k
>
> log n = k
>
> so the reccurence equation gives:
>
> = nT(1) +n*log(n)
>
> = n+ (n * log(n))
>
> So the mergesort complexity in the best case and in the worst case is:
>
> n * log(n)
>
> But the complexity of the quicksort in the worst case is:
>
> T(n)= n + T(n-1)
>
> it gives:
>
> T(n) = n + (n-1) + T(n-2)
>
> T(n) = n + (n-1) + (n-2)+ T(n-3)
>
> T(n) = 1 + 2+ 3+.+N
>
> T(n) = O(n^2)  // n power of 2
>
>
> You can download Parallel Sort library from:
>
> http://pages.videotron.com/aminer/
>
>
>
> Thank you,
> Amine Moulay Ramdane.
>
>
>
>
> 

Back to comp.programming.threads | Previous | Next — Previous in thread | Find similar

Thread

About my ParallelSort library "aminer" <aminer@toto.com> - 2012-10-31 19:21 -0500
  Re: About my ParallelSort library "aminer" <aminer@toto.com> - 2012-10-31 19:50 -0500
  Re: About my ParallelSort library "aminer" <aminer@toto.com> - 2012-10-31 20:40 -0500
  Re: About my ParallelSort library "aminer" <aminer@toto.com> - 2012-10-31 20:48 -0500
  Re: About my ParallelSort library "aminer" <aminer@toto.com> - 2012-10-31 21:08 -0500

csiph-web