473,322 Members | 1,699 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,322 software developers and data experts.

Complexety of algorithm

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
Nov 17 '05 #1
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

Nov 17 '05 #2
"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)
Nov 17 '05 #3
> 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)

Nov 17 '05 #4
"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
Nov 17 '05 #5
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

Nov 17 '05 #6
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


Nov 17 '05 #7


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

Nov 17 '05 #8

"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
Nov 17 '05 #9
"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
Nov 17 '05 #10

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

6
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...
16
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...
10
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,...
32
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...
113
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...
4
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...
2
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...
0
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...
1
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...
0
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...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
isladogs
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...
0
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...
0
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...
1
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)...
1
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...
1
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
0
isladogs
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...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.