Admittedly, my complexity course is behind me, but there seem to be a
few things wrong with your calculations of the efficiency. I'll try to
point out what I didn't like. If I'm wrong, please correct me.
On 2/10/07, Leonard Mada [EMAIL PROTECTED] wrote:
I have imagined a different algorithm,
On 02/09/2007 12:29 PM somebody named Prof J C Nash wrote:
The important issue is what conventions are used for time and rate.
About 25 years ago I tried to get information on this from Canadian
banks. Some were cooperative. As I recall, the three that responded used
three DIFFERENT rules.
Right, maybe my explanation was unclear. I'll try to repeat (and ask
other people to check my math).
On 2/10/07, Leonard Mada [EMAIL PROTECTED] wrote:
So, even in the worst scenario, this algorithm should work faster than
n* log(n). Also, (n/2 -1)! is worst case, when all residual elements
On Sat, 2007-10-02 at 02:41 +0200, Leonard Mada wrote:
John Machin wrote:
...
So who cares? The median value is 1. Is your alternative going to
return some value other than 1
Please define mathematically the middle value! It is NOT trivial as my
definitions showed. Anything else
Lets assume the following space A={1,2,3} [I do not know if it is called
space in English, probably NOT.]
Lets take the array 1,1,2,3,3,3
So the median is (2+3)/2 = 2.5 ? BUT the space A does NOT have the value
2.5. It is either 2 or 3. In this case, it is more appropriate to talk
about 2
On Sat, 2007-10-02 at 11:48 +0200, Uri David Akavia wrote:
While I'm not sure about revising the algorithm, you might be right
about the definition - define it as MEDIAN will return the value that
WOULD be in the middle IF sorted and then you won't force anyone to
sort. I still think most
Dear Uri,
you are very wrong.
I made some errors, too, so I repeat the calculations: (with n elements)
- initial sort: n/2 * log(n/2)
- 2 comparisons per remaining elements: 2*(n/2-1) = n - 2
- search position of new element: log[(n/2-1)!]log[(n/4)^(n/4)] =
n/4 * log(n/4)
- move array (with
