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
40  2193 
ravi wrote:
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.
Does this look like alt.do.my.homew ork?
First point - neither of the questions you have asked are specific to C
programming.
Second point - your homework assignments are intended to make you think,
do research and master the subject. It's not just about getting someone
to answer the questions for you.
On Aug 1, 6:32 am, ravi <dceravigu...@g mail.comwrote:
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.
What ideas do you have in mind so far? What sorting algorithms are you
familiar with?
Did you try them?
Ideally, a binary search tree could do the trick (Note however that in
some cases it might be O(n)!)
Abdo Haji-Ali
Programmer
In|Framez
In article <11************ **********@e9g2 000prf.googlegr oups.com>,
ravi <dc**********@g mail.comwrote:
>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.
Do you mean N + O(log N)? If not, what is n?
-- Richard
--
"Considerat ion shall be given to the need for as many as 32 characters
in some alphabets" - X3.4, 1963.
ravi wrote:
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.
Your notation is incorrect. You might mean O(N+log N), but that would
be O(N). Or N+log N, which is not correct. Or maybe approximately N +
k*log N.
--
Thad
In article <46************ ***********@aut h.newsreader.oc tanews.com>,
Thad Smith <Th*******@acm. orgwrote:
>Use only N + O(log n) comparisons to find the second largest (or
smallest) element in a list of N elements.
>Your notation is incorrect. You might mean O(N+log N), but that would
be O(N). Or N+log N, which is not correct. Or maybe approximately N +
k*log N.
What's wrong with N + O(log N) (assuming the n should be N)? It has a
perfectly well-defined meaning, that if you subtract N from the number
of comparisons, the result is O(log N).
-- Richard
--
"Considerat ion shall be given to the need for as many as 32 characters
in some alphabets" - X3.4, 1963.
On Wed, 01 Aug 2007 12:33:57 +0000, Richard Tobin wrote:
In article <46************ ***********@aut h.newsreader.oc tanews.com>,
Thad Smith <Th*******@acm. orgwrote:
>>Use only N + O(log n) comparisons to find the second largest (or
smallest) element in a list of N elements.
>>Your notation is incorrect. You might mean O(N+log N), but that would
be O(N). Or N+log N, which is not correct. Or maybe approximately N +
k*log N.
What's wrong with N + O(log N) (assuming the n should be N)? It has a
perfectly well-defined meaning, that if you subtract N from the number
of comparisons, the result is O(log N).
Convention is to count only the most significant factor; thus an algorithm
which runs in O(N) + 1000 time is an O(N) algorithm, the constant is
discarded.
In the description above, the function should run in N + O(log N) time.
As N increases, runtime increases in proportion to it, with log N adding a
small and ever less significant portion of the runtime; thus the O(log
n) is discarded and the algorithm is thus found to be O(N).
Kelsey Bjarnason wrote:
>
.... snip ...
>
Convention is to count only the most significant factor; thus an
algorithm which runs in O(N) + 1000 time is an O(N) algorithm, the
constant is discarded.
In the description above, the function should run in N + O(log N)
time. As N increases, runtime increases in proportion to it, with
log N adding a small and ever less significant portion of the
runtime; thus the O(log n) is discarded and the algorithm is thus
found to be O(N).
It's not a convention, it's reality. The technique is intended to
describe execution time required for large values of N. For large
enough N the value of log N is negligible, compared to N, and is
thus discarded.
--
"Vista is finally secure from hacking. No one is going to 'hack'
the product activation and try and steal the o/s. Anyone smart
enough to do so is also smart enough not to want to bother."
--
Posted via a free Usenet account from http://www.teranews.com
On Thu, 02 Aug 2007 15:57:48 -0700, Kelsey Bjarnason wrote:
On Wed, 01 Aug 2007 12:33:57 +0000, Richard Tobin wrote:
>In article <46************ ***********@aut h.newsreader.oc tanews.com>,
Thad Smith <Th*******@acm. orgwrote:
>>>Use only N + O(log n) comparisons to find the second largest (or
smallest) element in a list of N elements.
>>>Your notation is incorrect. You might mean O(N+log N), but that would
be O(N). Or N+log N, which is not correct. Or maybe approximately N +
k*log N.
What's wrong with N + O(log N) (assuming the n should be N)? It has a
perfectly well-defined meaning, that if you subtract N from the number
of comparisons, the result is O(log N).
Convention is to count only the most significant factor; thus an algorithm
which runs in O(N) + 1000 time is an O(N) algorithm, the constant is
discarded.
In the description above, the function should run in N + O(log N) time.
As N increases, runtime increases in proportion to it, with log N adding a
small and ever less significant portion of the runtime; thus the O(log
n) is discarded and the algorithm is thus found to be O(N).
Yes. time = N + O(log N) is abuse of notation. It should be
time - N = O(log N). But it is not something so strange.
For example sin(x) = x - x**3 / 3 + O(x**5) to mean that
sin(x) - x + x**3 / 3 is O(x**5). It is not so uncommon in general
(though it is the first time I've seen it for run times).
--
Army1987 (Replace "NOSPAM" with "email")
"Never attribute to malice that which can be adequately explained
by stupidity." -- R. J. Hanlon (?)
On Tue, 31 Jul 2007 21:32:58 -0700, ravi wrote:
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.
If the absolute value of the elements isn't too large, you can
use
if (a - b - abs(a - b))
/* a is greater than or equal to b */;
else
/* a is smaller than b */;
so you can do anything with 0 comparisons.
You can add for (i = 0; i < N - 1; i++) continue; to compare i
with N - 1 exactly N times, so the total number of comparisons is
N. Now 0 is O(log N), of course. (Yes, the compiler is allowed to
optimize it away, but what it does is OT here -- only the behavior
of the abstract machine, which compares i with N - 1 exactly N
times, is relevant. If this a problem, you can always declare i as
volatile...)
:-)
--
Army1987 (Replace "NOSPAM" with "email")
"Never attribute to malice that which can be adequately explained
by stupidity." -- R. J. Hanlon (?) 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: 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, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main usage, and What is the difference between ONU and Router. Let’s take a closer look !
Part I. Meaning of...
|
by: Hystou |
last post by:
Overview:
Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For most users, this new feature is actually very convenient. If you want to control the update process,...
| | |
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: TSSRALBI |
last post by:
Hello
I'm a network technician in training and I need your help.
I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs.
The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols.
I succeeded, with both firewalls in the same network. But I'm wondering if it's possible to do the same thing, with 2 Pfsense firewalls...
|
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.
| |
