How I can find median (middle element) in T(n) = O(n) int the worst case?
--
Marcin
8  1431 
Marcin wrote:
How I can find median (middle element) in T(n) = O(n) int the
worst case?
By asking in a newsgroup where it is topical, such as
comp.programming. You probably won't like the answer.
--
"If you want to post a followup via groups.google.com, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson
Hi
Marcin wrote: How I can find median (middle element) in T(n) = O(n) int the worst case?
Off-Topic, but google for "selection algorithm", "kth element O(n)".
Or have a look here: http://www.ics.uci.edu/~eppstein/161/960130.html.
Be aware though that the algorithm performs worse than sorting in O(n log n)
for reasonable amounts of data.
Markus
"Marcin" <se*******@o2.pl> wrote in message
news:d3**********@news.dialog.net.pl... How I can find median (middle element) in T(n) = O(n) int the worst case?
--
Marcin
This depends on what O(n) means, comparisons, moves, passes over the data
etc...
I think you are impying comparisons, in which case it cannot be done.
On Fri, 15 Apr 2005 23:16:50 -0500, "BGreene" <ba****@highstream.net>
wrote:
"Marcin" <se*******@o2.pl> wrote in message
news:d3**********@news.dialog.net.pl... How I can find median (middle element) in T(n) = O(n) int the worst case?
--
Marcin
This depends on what O(n) means, comparisons, moves, passes over the data
etc...
I think you are impying comparisons, in which case it cannot be done.
As it happens the subject is off topic and your reply is incorrect;
the median can be found using worst case O(n) comparisons.
Richard Harter, cr*@tiac.net http://home.tiac.net/~cri, http://www.varinoma.com
Save the Earth now!!
It's the only planet with chocolate.
Richard Harter wrote: On Fri, 15 Apr 2005 23:16:50 -0500, "BGreene" <ba****@highstream.net>
wrote:
"Marcin" <se*******@o2.pl> wrote in message
news:d3**********@news.dialog.net.pl...
How I can find median (middle element) in T(n) = O(n) int the worst case?
--
Marcin
This depends on what O(n) means, comparisons, moves, passes over the data
etc...
I think you are impying comparisons, in which case it cannot be done.
As it happens the subject is off topic and your reply is incorrect;
the median can be found using worst case O(n) comparisons.
btw, each deterministic algorithm requires at least 2n
comparisons in worst case to find the median (currently the best known
requires det. alg. requires about 2.95n comparisons).
A very simple randomized algorithm finds the median with at most
1.5n + o(n) comparisons with prob. 1-n^(1/4).
Regards,
Daniel
Richard Harter, cr*@tiac.net
http://home.tiac.net/~cri, http://www.varinoma.com
Save the Earth now!!
It's the only planet with chocolate.
I apologize for this ignorant post. I was thinking n comparsions not O(n).
Next time I'll keep my keyboard quiet :-).
Barry
"BGreene" <ba****@highstream.net> wrote in message
news:11*************@corp.supernews.com...
"Marcin" <se*******@o2.pl> wrote in message
news:d3**********@news.dialog.net.pl... How I can find median (middle element) in T(n) = O(n) int the worst
case?
--
Marcin
This depends on what O(n) means, comparisons, moves, passes over the data
etc...
I think you are impying comparisons, in which case it cannot be done.
BGreene wrote:
I apologize for this ignorant post.
I was thinking n comparsions not O(n).
Next time I'll keep my keyboard quiet :-).
This depends on what O(n) means,
comparisons, moves, passes over the data
etc...
I think you are impying comparisons,
in which case it cannot be done.
Big O refers to the dominant term
of the equation which governs the running time.
--
pete
On Thu, 28 Apr 2005 12:28:57 -0500, "BGreene" <ba****@highstream.net>
wrote: I apologize for this ignorant post. I was thinking n comparsions not O(n).
Next time I'll keep my keyboard quiet :-).
No problem. It's not at all obvious (until you think of the trick)
that it can be done in guaranteed O(n) comparisons. The best
published algorithms involve dancing widdershins and flapping your
arms chicken style.
Richard Harter, cr*@tiac.net http://home.tiac.net/~cri, http://www.varinoma.com
Save the Earth now!!
It's the only planet with chocolate. This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics
by: Ross Contino |
last post by:
Hello to all:
I have been searching the web for examples on how to determine a median
value in a mySQL table. I have reviewed the article at...
|
by: Hugo L. |
last post by:
I really don't know how to calculate the median. Can anybody help me?
|
by: Bob |
last post by:
I have been looking at the code for MedianFind(pDte As String) from the
following thread from UtterAccess.com: "Finding Median average grouped
by field"
I have been able to get it to run using...
|
by: nick.vitone |
last post by:
Hi,
I'm somewhat of a novice at Access, and I have no experience
programming whatsoever. I'm attempting to calculate the statistical
median in a query. I need to "Group by" one column and find...
|
by: uspensky |
last post by:
I have a table (cars) with 3 fields:
VIN, Class, sell_price
101, sports, 10000
102, sports, 11000
103, luxury, 9000
104, sports, 11000
105, sports, 11000
106, luxury, 5000
107, sports, 11000
|
by: jonm4102 |
last post by:
I'm trying to calculate the median of some numerical data. The data can
only be found in a query (henceforth query 1) field I previously made,
and I would prefer to calculate the median in a new...
|
by: Scott |
last post by:
I need to take the median from a field of records in a report. Can someone
shed the light how to do it.
Thanks,
Scott
|
by: Bhadan |
last post by:
Hello,
I have several jagged arrays which have been sorted.
I'm trying to find the median of each array. Any tips appreciated.
TIA.
Bhads.
|
by: mehwishobaid |
last post by:
i dont know wat is wrong with my code. when i compile. i get the error
saying line 29: error: expression must have pointer-to-object type
#include <iostream>
using namespace std;
#include...
|
by: rrstudio2 |
last post by:
I am using the following vba code to calculate the median of a table
in MS Access:
Public Function MedianOfRst(RstName As String, fldName As String) As
Double
'This function will calculate the...
|
by: Charles Arthur |
last post by:
How do i turn on java script on a villaon, callus and itel keypad mobile phone
|
by: ryjfgjl |
last post by:
If we have dozens or hundreds of excel to import into the database, if we use the excel import function provided by database editors such as navicat, it will be extremely tedious and time-consuming...
|
by: emmanuelkatto |
last post by:
Hi All, I am Emmanuel katto from Uganda. I want to ask what challenges you've faced while migrating a website to cloud.
Please let me know.
Thanks!
Emmanuel
|
by: BarryA |
last post by:
What are the essential steps and strategies outlined in the Data Structures and Algorithms (DSA) roadmap for aspiring data scientists? How can individuals effectively utilize this roadmap to progress...
|
by: nemocccc |
last post by:
hello, everyone, I want to develop a software for my android phone for daily needs, any suggestions?
|
by: Hystou |
last post by:
There are some requirements for setting up RAID:
1. The motherboard and BIOS support RAID configuration.
2. The motherboard has 2 or more available SATA protocol SSD/HDD slots (including MSATA, M.2...
|
by: marktang |
last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However,...
|
by: Oralloy |
last post by:
Hello folks,
I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>".
The problem is that using the GNU compilers,...
|
by: tracyyun |
last post by:
Dear forum friends,
With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each...
| |
