Re^2: perl threads and dual core hyper-threading

That's is a O(2n!) (factorial) process where n is the number of threads.

It's just a minor detail (since O(n) is much better than O(n^2)), but I don't see where you get that factorial.

  O( 2n + 2(n-1) + 2(n-2) + ... + 2(2) + 2(1) )

          2n + 2(n-1) + 2(n-2) + ... + 2(2) + 2(1)
        = 2(n + n-1 + n-2 + ... + 2 + 1)
        = 2(n*(n+1)/2)
        = n^2 + n

= O( n^2 + n )
= O( n^2 )
[download]

Or if you ignore the fact that the list is shrinking:

  O( n * 2n )
= O( 2n^2 )
= O( n^2 )
[download]

Comment on Re^2: perl threads and dual core hyper-threading Select or Download Code

Replies are listed 'Best First'.
Re^3: perl threads and dual core hyper-threading by BrowserUk (Patriarch) on Apr 25, 2006 at 23:05 UTC
You're right. It's additive not multiplicative, so O(n*(n-1)). Near as damn it n^2 as you said. Still bloody wasteful ;) Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error. Lingua non convalesco, consenesco et abolesco. -- Rule 1 has a caveat! -- Who broke the cabal? "Science is about questioning the status quo. Questioning authority". In the absence of evidence, opinion is indistinguishable from prejudice.	[reply] [d/l]

Replies are listed 'Best First'.

Re^3: perl threads and dual core hyper-threading
by BrowserUk (Patriarch) on Apr 25, 2006 at 23:05 UTC

You're right. It's additive not multiplicative, so O(n*(n-1)). Near as damn it n^2 as you said. Still bloody wasteful ;)

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.

Lingua non convalesco, consenesco et abolesco. -- Rule 1 has a caveat! -- Who broke the cabal?

"Science is about questioning the status quo. Questioning authority".

In the absence of evidence, opinion is indistinguishable from prejudice.

[reply]
[d/l]