Hi
I'm trying to calculate a complexety of an algorithm what does the sum
1*log(1) + 2*log(2) + ... + (n-1)*log(n-1) + n*log(n)
give in O()?
I'm guession it's O(log(n)*n^2) but is it?
Kind Regards,
Allan Ebdrup 9 1268
Assuming that the log() function is itself O(1), then the complexity
should be O(n).
Further, It's been a long time since I've done such things, but I
suspect that there a formula which replaces the loop, and reduces it to
O(1).
--
--
Truth,
James Curran
[erstwhile VC++ MVP]
Home: www.noveltheory.com Work: www.njtheater.com
Blog: www.honestillusion.com Day Job: www.partsearch.com
"Allan Ebdrup" <co****@ofir.com> wrote in message
news:#j**************@tk2msftngp13.phx.gbl... Hi I'm trying to calculate a complexety of an algorithm what does the sum 1*log(1) + 2*log(2) + ... + (n-1)*log(n-1) + n*log(n) give in O()? I'm guession it's O(log(n)*n^2) but is it?
Kind Regards, Allan Ebdrup
"James Curran" <ja*********@mvps.org> wrote in message
news:%2****************@TK2MSFTNGP09.phx.gbl... Assuming that the log() function is itself O(1), then the complexity should be O(n).
the log part has at least O(log(n)) complexety and the 1+2+3+...+n is O(n^2)
> the log part has at least O(log(n)) complexety
Whatever gave you that idea? Consider the following:
f(n) = n * 1000000000. What is the complexity of f(n). O(1 billion
n) ? O(n)? Actually, it's just O(1), because there is exactly one step to
be done calculate the value. There will always be just one step regardly of
the value of n. and the 1+2+3+...+n is O(n^2)
Again nonsense. It's *result* is in the range of n^2, but the process
to calculate it involves n steps, and therefore is O(n):
int sum = 0;
for(int i = 1; i <= n; ++i)
{
sum += i;
}
In fact, that particular summation is what I was thinking of when I
mentioned an algorithm of O(1). Summing 1...n as I did above is O(n), but
as Gauss proved as a child the same answer can be achieve via:
f(n) = ((n +1) * (n / 2)
which is of O(1) (the number of steps is unrelated to the value of n)
--
--
Truth,
James Curran
[erstwhile VC++ MVP]
Home: www.noveltheory.com Work: www.njtheater.com
Blog: www.honestillusion.com Day Job: www.partsearch.com
"Allan Ebdrup" <co****@ofir.com> wrote in message
news:#a**************@TK2MSFTNGP10.phx.gbl... "James Curran" <ja*********@mvps.org> wrote in message news:%2****************@TK2MSFTNGP09.phx.gbl... Assuming that the log() function is itself O(1), then the complexity should be O(n). the log part has at least O(log(n)) complexety and the 1+2+3+...+n is
O(n^2)
"James Curran" <ja*********@mvps.org> wrote in message
news:eJ**************@TK2MSFTNGP15.phx.gbl... the log part has at least O(log(n)) complexety
Whatever gave you that idea? Consider the following: f(n) = n * 1000000000. What is the complexity of f(n). O(1 billion n) ? O(n)? Actually, it's just O(1), because there is exactly one step to be done calculate the value. There will always be just one step regardly of the value of n. and the 1+2+3+...+n is O(n^2) Again nonsense. It's *result* is in the range of n^2, but the process to calculate it involves n steps, and therefore is O(n): int sum = 0; for(int i = 1; i <= n; ++i) { sum += i; }
In fact, that particular summation is what I was thinking of when I mentioned an algorithm of O(1). Summing 1...n as I did above is O(n), but as Gauss proved as a child the same answer can be achieve via:
f(n) = ((n +1) * (n / 2)
which is of O(1) (the number of steps is unrelated to the value of n)
Well you seem to have misunderstood the question, the sum I'm adding
represents steps in an algorithm so when I write n*log(n) thats O(n*log(n)),
the sum represents calling an algorithm that's O(n*log(n)) n times, with 1
to n elements.
Kind Regars,
Allan Ebdrup
So, let's see if I get this straight: When you stated: I'm trying to calculate a complexety of an algorithm what does the sum 1*log(1) + 2*log(2) + ... + (n-1)*log(n-1) + n*log(n) give in O()?
You actually meant that you want to calculate the complexety of an algorithm
which does the sum:
1*f(1) + 2*f(2) + ... + (n-1) * f(n-1) + n* f(n), where f(n) has a
complexity of O(n*log(n)).
If that is the case (you are sorting increasingly larger arrays?), then the
overall complexity would be O(Log(n) *n ^2)
--
--
Truth,
James Curran
[erstwhile VC++ MVP]
Home: www.noveltheory.com Work: www.njtheater.com
Blog: www.honestillusion.com Day Job: www.partsearch.com
"Allan Ebdrup" <co****@ofir.com> wrote in message
news:u8**************@TK2MSFTNGP14.phx.gbl... "James Curran" <ja*********@mvps.org> wrote in message news:eJ**************@TK2MSFTNGP15.phx.gbl... the log part has at least O(log(n)) complexety Whatever gave you that idea? Consider the following: f(n) = n * 1000000000. What is the complexity of f(n). O(1 billion n) ? O(n)? Actually, it's just O(1), because there is exactly one
step to be done calculate the value. There will always be just one step
regardly of the value of n. and the 1+2+3+...+n is O(n^2)
Again nonsense. It's *result* is in the range of n^2, but the
process to calculate it involves n steps, and therefore is O(n): int sum = 0; for(int i = 1; i <= n; ++i) { sum += i; }
In fact, that particular summation is what I was thinking of when I mentioned an algorithm of O(1). Summing 1...n as I did above is O(n),
but as Gauss proved as a child the same answer can be achieve via:
f(n) = ((n +1) * (n / 2)
which is of O(1) (the number of steps is unrelated to the value of n)
Well you seem to have misunderstood the question, the sum I'm adding represents steps in an algorithm so when I write n*log(n) thats
O(n*log(n)), the sum represents calling an algorithm that's O(n*log(n)) n times, with 1 to n elements.
Kind Regars, Allan Ebdrup
Allan,
I believe you are correct. The complexity is O(n^2*log(n)).
Let g(x) = x*log(x)
and
Let f(x) = Sum[g(x), x=1, n] = 1*log(1) + 2*log(2) + ... + n*log(n)
The following inequality is immediately obvious.
n*log(n) < f(n) < n^2*log(n)
That narrows things down a little bit, but we need to go further. We
can do this by integrating g(x) to approximate f(x).
x^2 x^2
So f(x) = Integral[g(x), dx] = --- log(x) - --- + E
2 4
I used integration by parts to integrate x*log(x). E is some error
term which I believe you can approximate and convince yourself that is
negligible by using the Euler-MacLaurin Formula.
Therefore, f(x) has O(n^2*log(n)) complexity.
Perhaps someone who is much better at math can verify this?
Brian
Allan Ebdrup wrote: Hi I'm trying to calculate a complexety of an algorithm what does the sum 1*log(1) + 2*log(2) + ... + (n-1)*log(n-1) + n*log(n) give in O()? I'm guession it's O(log(n)*n^2) but is it?
Kind Regards, Allan Ebdrup
Brian Gideon wrote: x^2 x^2 So f(x) = Integral[g(x), dx] = --- log(x) - --- + E 2 4
For those not using a fixed-width font:
f(x) = Integral[g(x), dx] = (x^2/2)*log(x) - (x^2/4) + E
"James Curran" <ja*********@mvps.org> wrote in message
news:em**************@TK2MSFTNGP09.phx.gbl... So, let's see if I get this straight: When you stated:
I'm trying to calculate a complexety of an algorithm what does the sum 1*log(1) + 2*log(2) + ... + (n-1)*log(n-1) + n*log(n) give in O()?
You actually meant that you want to calculate the complexety of an algorithm which does the sum: 1*f(1) + 2*f(2) + ... + (n-1) * f(n-1) + n* f(n), where f(n) has a complexity of O(n*log(n)).
If that is the case (you are sorting increasingly larger arrays?), then the overall complexity would be O(Log(n) *n ^2)
Yes, as I write I wanted to know:
what does the sum
1*log(1) + 2*log(2) + ... + (n-1)*log(n-1) + n*log(n)
give in O()?
Kind Regards,
Allan Ebdrup
"James Curran" <ja*********@mvps.org> wrote in message
news:em**************@TK2MSFTNGP09.phx.gbl... You actually meant that you want to calculate the complexety of an algorithm which does the sum: 1*f(1) + 2*f(2) + ... + (n-1) * f(n-1) + n* f(n), where f(n) has a complexity of O(n*log(n)).
If that is the case (you are sorting increasingly larger arrays?), then the overall complexity would be O(Log(n) *n ^2)
Actually I'm not doing the sum, I'm sorting increasingly larger arrays as
you state (or another programmer was), but I've found a different approach
that's O(n*log(n))
Kind Regards,
Allan Ebdrup This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics
by: Jack Smith |
last post by:
Hello, any help appreciated with following problem. I figured out the
algorithm (I think), just having trouble proving it is optimal.
Suppose we are given n tasks each of which takes 1 unit...
|
by: cody |
last post by:
I have to write an algorithm with must ensure that objects are put in
buckets (which are always 4 in size).
The objects have two properties: A and B. It is not allowed that in a bucket
are objects...
|
by: bpontius |
last post by:
The GES Algorithm
A Surprisingly Simple Algorithm for Parallel Pattern Matching
"Partially because the best algorithms presented in the literature
are difficult to understand and to implement,...
|
by: Cmorriskuerten |
last post by:
HI,
is this is this solution to test if a number is a prime number or not:
/*
* Is n a prime number?
* Return TRUE (1): n is a prime number
* Return FALSE (0): n is a *not* a prime number...
|
by: Bonj |
last post by:
I was in need of an encryption algorithm to the following requirements:
1) Must be capable of encrypting strings to a byte array, and decyrpting
back again to the same string
2) Must have the same...
|
by: FBM |
last post by:
Hi,
I am working on a program that simulates one of the elements of ATM.
The simulation stores events which occurs every some milliseconds for a
certain amount of time. Every time that an event...
|
by: Julio C. Hernandez Castro |
last post by:
Dear all,
We have just developped a new block cipher called Raiden, following a
Feistel Network structure by means of genetic programming. Our
intention now consists on getting as much feedback...
|
by: aruna |
last post by:
hey guys i earlier had very valuable responses from you all for base64
encoding algorithm.so thank for that. so now i need your assistance to
do a float encoding algorithm. you may wonder why i'm...
|
by: almurph |
last post by:
Hi everyone,
Concerning the Needleman-Wunsch algorithm (cf.
http://en.wikipedia.org/wiki/Needleman-Wunsch_algorithm) I have
noticed a possible loop.
Inside the algorithm there is an...
|
by: DolphinDB |
last post by:
Tired of spending countless mintues downsampling your data? Look no further!
In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
|
by: ryjfgjl |
last post by:
ExcelToDatabase: batch import excel into database automatically...
|
by: isladogs |
last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM).
In this month's session, we are pleased to welcome back...
|
by: Vimpel783 |
last post by:
Hello!
Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
|
by: ArrayDB |
last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
|
by: PapaRatzi |
last post by:
Hello,
I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
|
by: CloudSolutions |
last post by:
Introduction:
For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
|
by: Defcon1945 |
last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
|
by: isladogs |
last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 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 former...
| |