# Re: What is Complexity?

c.lang.myself@xxxxxxxxx said:

What is complexity of this algorithm:

int fun(int i)
{
int temp=0;
if((i==0)||(i==1))
return 1;
for(int n=1;n<i;n++)
{
temp+=fun(n)*fun(i-n);
}
return temp;
}

If you don't know, one good way to find out is to graph it for a small
range of values, and then try some obvious divisors (the value itself, its
square, its log, etc), and see if you get any straight lines - or
straight-ish, at least.

Use that assumed complexity relation to do some predictions on big numbers,
and see how it stands up to reality.

Alternatively (for experts only), dig out Knuth.

--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
"Usenet is a strange place" - dmr 29 July 1999
.

## Relevant Pages

• Re: looking for a random function
... > random positive integer number, say, between 1 and n, n being a positive ... > int nrand ... I think your algorithm can be expressed a little more naturally as: ... rather than a straight line. ...
(comp.programming)
• Re: Instance and Inheritance Question
... the formal constructor parameters and goes straight to the base class ... It just didn't make sense to say it went straight there. ... It looks like DatePlus requires certain parameters (int year, ... it would die and nevery make it to the base class constructor. ...
(microsoft.public.dotnet.languages.csharp)
• Re: I Am Now Physically Forced To Replay Fallout 1, Thanks Alot
... low stats, such as an IQ of 3, had some special events waiting for them. ... I've always gone straight for INT 10 and AGI 10, to get those skill points and action points. ...
(comp.sys.ibm.pc.games.rpg)
• Re: K&R exercise 1-18
... int main ... Let's see if I got this straight: ... function takes no arguments and has a prototype. ... This is an invalid C program, has undefined behaviour, but does not ...
(comp.lang.c)
• Re: Checking if a table exists, so that it may be dropped before recreating it
... This is the method SQL Server uses when it generates scripts. ... "Dr Tarheel" wrote in message ... I'd like to skip the DROP TABLE command and go straight to the ...
(microsoft.public.sqlserver.programming)