Can anybody tell me a method to
Use only N + O(log n) comparisons to find the second largest (or
smallest) element in a list of N elements.
Thnx in advance
Aug 1 '07
40  2223 
Keith Thompson wrote On 08/09/07 13:17,:
Eric Sosman <Er*********@su n.comwrites:
[...]
> Perhaps our entire set-to has just been a confusion
about the subject matter, causing us to use the same words
with different referents. If so, I apologize for my heat,
and to atone for any offense I offer you ein Gift.
;-)
Um, do you know what "ein Gift" means in German?
Ja. Ich schrieb es, um die Mehrdeutigkeit von
Wörtern zu zeigen. (Beachten Sie das Lächeln.)
-- Er*********@sun .com
Kelsey Bjarnason <kb********@gma il.comwrote:
On Thu, 09 Aug 2007 08:45:37 +0000, Richard Bos wrote:
Ah well, off to sort a card deck using heapsort. All in a day's work.
No, no. Use a bubble sort, just one with a small constant overhead per
item.
You know what? If I ever found a bubble sort that had a smaller K than
the equivalent insertion sort, I _would_ use it.
Richard
On Fri, 10 Aug 2007 06:43:17 +0000, Richard Bos wrote:
Kelsey Bjarnason <kb********@gma il.comwrote:
>On Thu, 09 Aug 2007 08:45:37 +0000, Richard Bos wrote:
Ah well, off to sort a card deck using heapsort. All in a day's work.
No, no. Use a bubble sort, just one with a small constant overhead per
item.
You know what? If I ever found a bubble sort that had a smaller K than
the equivalent insertion sort, I _would_ use it.
If you're talking of *real* cards, that's unlikely, given that the
equivalent of memmove() can be done in O(1). :-)
--
Army1987 (Replace "NOSPAM" with "email")
No-one ever won a game by resigning. -- S. Tartakower
In article <pa************ *************** @NOSPAM.it>,
Army1987 <ar******@NOSPA M.itwrote:
>If you're talking of *real* cards, that's unlikely, given that the
equivalent of memmove() can be done in O(1). :-)
Really? How fast can you move 10^10 cards?
-- Richard
--
"Considerat ion shall be given to the need for as many as 32 characters
in some alphabets" - X3.4, 1963.
On Fri, 10 Aug 2007 09:26:37 +0000, Richard Tobin wrote:
In article <pa************ *************** @NOSPAM.it>,
Army1987 <ar******@NOSPA M.itwrote:
>>If you're talking of *real* cards, that's unlikely, given that the
equivalent of memmove() can be done in O(1). :-)
Really? How fast can you move 10^10 cards?
It depends on the speed of the truck they're contained in. :-)
If it is traveling at 50 km/h (14 m/s), it takes me 7e-5 seconds
to move them by one millimeter.
No, you didn't mean this...
Well, if I have 10 billion cards, and insert a card in position
3, the third card becomes the fourth card, the fourth card becomes
the fifth card and so on. It doesn't take much longer than if the
cards were ten.
--
Army1987 (Replace "NOSPAM" with "email")
No-one ever won a game by resigning. -- S. Tartakower ri*****@cogsci. ed.ac.uk (Richard Tobin) wrote:
In article <pa************ *************** @NOSPAM.it>,
Army1987 <ar******@NOSPA M.itwrote:
If you're talking of *real* cards, that's unlikely, given that the
equivalent of memmove() can be done in O(1). :-)
Really? How fast can you move 10^10 cards?
The largest deck I own is a tarot deck of 73 cards; I've used double
normal decks of /in toto/ 104 cards; but I've never seen a deck of
10**10 cards.
Which was kinda my point all along, really. Yes, Big-O notation is all
about big numbers; but how often do you really encounter datasets of
10**10 members in practice? I know I never have. Hundreds of thousands,
yes, although usually safely packed away inside a database. Dozens or
hundreds is much, much more likely. Therefore, although Big-O notation
is a good tool for information _science_, in the reality of computing
_practice_ the constant factors are often at least as important as the
asymptotical behaviour.
Richard
In article <pa************ *************** *@NOSPAM.it>,
Army1987 <ar******@NOSPA M.itwrote:
>Really? How fast can you move 10^10 cards?
It depends on the speed of the truck they're contained in. :-)
If it is traveling at 50 km/h (14 m/s), it takes me 7e-5 seconds
to move them by one millimeter.
That's thoughput; consider latency: if a card weighs a gram, 10^10
weigh 10,000 tons. How fast can you accelerate that lot?
>Well, if I have 10 billion cards, and insert a card in position
3, the third card becomes the fourth card, the fourth card becomes
the fifth card and so on. It doesn't take much longer than if the
cards were ten.
Consider the force needed to insert a card at the 5-billionth position.
-- Richard
--
"Considerat ion shall be given to the need for as many as 32 characters
in some alphabets" - X3.4, 1963.
On Fri, 10 Aug 2007 10:54:37 +0000, Richard Tobin wrote:
In article <pa************ *************** *@NOSPAM.it>,
Army1987 <ar******@NOSPA M.itwrote:
>>Really? How fast can you move 10^10 cards?
It depends on the speed of the truck they're contained in. :-)
If it is traveling at 50 km/h (14 m/s), it takes me 7e-5 seconds
to move them by one millimeter.
That's thoughput; consider latency: if a card weighs a gram, 10^10
weigh 10,000 tons. How fast can you accelerate that lot?
Good point. Maybe O(1) was too optimistic, but of course it
doesn't take one billion times longer than to move ten cards.
Maybe O(log N)?
Anyway, I don't think this could ever cause a bubble sort to be
faster than insertion sort. Also because swapping the 321495013th
card with the 6138274597th one can take a nontrivial amount of
time...
>>Well, if I have 10 billion cards, and insert a card in position
3, the third card becomes the fourth card, the fourth card becomes
the fifth card and so on. It doesn't take much longer than if the
cards were ten.
Consider the force needed to insert a card at the 5-billionth position.
It depends on how tightly packed they are. If they are loosely
packed enough, it will not be excessive. Only that just a few
cards are physically moved; but the indices of five billion cards
change very quickly.
(More seriously, whilst *notationally* the big-O notation is for
asymptotic growth as N approaches infinity, *in practice* it just
means "as N becomes large enough that additive constants can be
neglected". For example, when N becomes larger than (size_t)(-1),
a C implementation of a sorting algorithm becomes *very* tricky,
but this isn't usually an issue, even when considering the big-O
notation.)
--
Army1987 (Replace "NOSPAM" with "email")
No-one ever won a game by resigning. -- S. Tartakower
Army1987 wrote:
On Fri, 10 Aug 2007 06:43:17 +0000, Richard Bos wrote:
.... snip ...
>
>You know what? If I ever found a bubble sort that had a smaller
K than the equivalent insertion sort, I _would_ use it.
If you're talking of *real* cards, that's unlikely, given that
the equivalent of memmove() can be done in O(1). :-)
memmove has O(N) performance. Considerably different than O(1).
--
Chuck F (cbfalconer at maineline dot net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home .att.net>
--
Posted via a free Usenet account from http://www.teranews.com
On Aug 10, 4:03 am, r...@hoekstra-uitgeverij.nl (Richard Bos) wrote:
rich...@cogsci. ed.ac.uk (Richard Tobin) wrote:
In article <pan.2007.08.10 .09.29.45.29... @NOSPAM.it>,
Army1987 <army1...@NOSPA M.itwrote:
>If you're talking of *real* cards, that's unlikely, given that the
>equivalent of memmove() can be done in O(1). :-)
Really? How fast can you move 10^10 cards?
The largest deck I own is a tarot deck of 73 cards; I've used double
normal decks of /in toto/ 104 cards; but I've never seen a deck of
10**10 cards.
Which was kinda my point all along, really. Yes, Big-O notation is all
about big numbers; but how often do you really encounter datasets of
10**10 members in practice? I know I never have. Hundreds of thousands,
yes, although usually safely packed away inside a database. Dozens or
hundreds is much, much more likely. Therefore, although Big-O notation
is a good tool for information _science_, in the reality of computing
_practice_ the constant factors are often at least as important as the
asymptotical behaviour.
I see sets in hundreds of millions and billions all the time.
For instance, all registered products of a large software company.
For instance, all individual tolls taken on toll roads in New Jersey
over the last decade.
For instance, DNA sequences for the human genome.
Database work often entails many terabytes of data. So we had better
care about big-O.
On the other hand (as you say) a hybrid algorithm is usually the best,
because it can have the best of all worlds. This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics | |
by: news1.on.sympatico.ca |
last post by:
what is the literal for the largest character value in java?
ie.
111 in binary is representing 7 (4+2+1) <-- this is 3 bit
now java is 32 or 64 bit
what is the largest character value ?
thanks
|
by: Keke922 |
last post by:
I have to write a program that allows the user to enter a series of integers
and -99 when they want to exit the loop. How do I display the largest and
smallest number the user entered?
|
by: Jaspreet |
last post by:
I was working on some database application and had this small task of
getting the second highes marks in a class. I was able to do that using
subqueries.
Just thinking what is a good way of getting second highest value in an
integer array. One method I know of is to make the 1st pass through the
array and find the highest number. In the second pass we can find the
highest number which is less than the number we obtained in the 1st
pass.
|
by: thomasp |
last post by:
For those who gave advice on the shortfalls of my first attempt at writing a
vb.net class, Thank You.
I hope that I was able to apply some of your advice to this larger atempt.
At first I didn' t really see an
advantage of a Class over a module containing the same functions, but now
that this Class is working
for me, I have found a possible use. Since this class will hold all the
values used in a report I am
building, I think I will now...
|
by: Rajesh |
last post by:
Hello Everybody,
Can anybody help me to write a C program for finding the second largest
element in an array.
without using any sort algo. The array may conatin duplicate elements.
The algo should run in O(n) time.
Rajesh
| | |
by: HEMH6 |
last post by:
Who can help solve this problem???
Finding the Largest Value
(a) write a function, largest(), that returns the largest value in a signed integer array. The array and its size are passed as arguments.
(b)Write a main program that inputs MAX values from the keyboard into a signed
integer array, array, and points, using largest(), the largest value to the screen.
|
by: bele_harshad2006 |
last post by:
how can i pick up largest no from 5 rows by 5 column matrix????
|
by: pichukakiran |
last post by:
Query how to get second and third largest values from database
|
by: crystal2005 |
last post by:
I am writing a program that receive maximum of 25 line of string each has 20 characters maximum. The program will print the smallest and the largest string. However the following program gives me Segmentation fault (core dumped) :(( It looks simple but i have no idea what went wrong....
Can anyone help me out??
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAX_INPUT 25
|
by: Hystou |
last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it.
First, let's disable language synchronization. With a Microsoft account, language settings sync across devices. To prevent any complications,...
|
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, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed.
This is as boiled down as I can make it.
Here is my compilation command:
g++-12 -std=c++20 -Wnarrowing bit_field.cpp
Here is the code in...
| | |
by: jinu1996 |
last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that captivates audiences and drives business growth.
The Art of Business Website Design
Your website is...
|
by: agi2029 |
last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then launch it, all on its own....
Now, this would greatly impact the work of software developers. The idea...
|
by: isladogs |
last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM).
In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules.
He will explain when you may want to use classes instead of User Defined Types (UDT). For example, to manage the data in unbound forms.
Adolph will...
|
by: conductexam |
last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one.
At the time of converting from word file to html my equations which are in the word document file was convert into image.
Globals.ThisAddIn.Application.ActiveDocument.Select();...
|
by: adsilva |
last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
|
by: 6302768590 |
last post by:
Hai team
i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
| | |
by: muto222 |
last post by:
How can i add a mobile payment intergratation into php mysql website.
| |
