By whazat (Sat Jan 17, 2004 at 03:13:10 AM EST) (all tags)
Branching from a previous challenge answer we came accross the problem of calculating the complexity of a certain function.

I have found a formula for that function, now all I need is the complexity class or  mathematical name for the function.

See inside for details, links to nude women*, bo staff stuff and dodgy IT training places.

The matrix of the result looks something like this.

| 0 1  2 3   4  5 6 7 8 9
---------------------------

1.  | 1 1  1 1   1  1 1 1 1 1
2.  | 1 2  3 4   5  6 7 8 9
3.  | 1 3  6 10 15 ............
4.  | 1 4 10 20 ................
5.  | 1 5 15 35.................
Meh damn autoformat.
The recursive function for this is F(x,y) = F(x-1,y) + F(x, y-1) unless x or y are zero in which case it returns 1. We were interested in the growth of y = 26, because we have 26

Now you may have noticed that this is very similar to pascals triangle (not the fibonacci series as I said earlier, I always get them confused).

So I monkied around with the pascal triangle formula and got this.
F(x,y) = (x + y)!/ (x!*y!)

While x! grows faster than 2x this function doesn't grow so fast.

So what I am wondering is if there is any further work on this sort of problems.

Other things I have been doing, fiddling about with a branch I found in order to turn it into a bo staff so I can practise and get up at god awful hours and pretend I am hardcore. I refuse to spend lots of money on something I will likely get bored of at some point.

Also this week went to IT training place in Tolworth that said they will train me for \$LOTS of money. If I get to a high enough level of training they will guarantee me a job or my money back. I don't know the full details but it sounds dodgy to me so I an stringing them along until I find the details.

Complexity Question | 2 comments (2 topical, 0 hidden)
Well, by gazbo (5.00 / 1) #1 Sat Jan 17, 2004 at 04:38:06 AM EST
I'm not in a mathy frame of mind at the moment, so I'm not sure how to accurately phrase it, but the order is clearly exponential: when x=0, F(y) is constant. When x=1, F(y) is first order. When x=2, F(y) is 2nd order. In other words, it grows as yx.

Of course the tricky part in my current frame of mind is that the converse is also true - i.e. if we look at fixed y, we see that F(x) is xy. So, I can't think of a snappy way of writing it in big-oh notation, but I have a feeling that it will just turn out to be exponential. Hell, maybe it's even impossible to write an expression without considering one of the variables as constant.

I recommend always assuming 7th normal form where items in a text column are not allowed to rhyme.

Not exponential by whazat (3.00 / 0) #2 Sat Jan 17, 2004 at 06:06:12 AM EST
Polynomial at least when we fix one of the numbers as we do in scrabble to 26. It will be proportional to 1026 to go down 10 levels, rather than 2610. If it was exponential F(5, 5) would be a lot higher than 252, or to put another way F(10,26) is only 2.54 * 108. Rather than 2610  which would be exponential and 1.41 * 1014