This is readable and just fine if you are handing it in for a class.
The benefit of the pascal triangle is that through a simple number triangle you can find binomial coefficients. It has since been redefined as the binomial coefficient. But historically it was interesting because it could provide binomial coefficients through simpler math than n choose k.
If you have to calculate the whole triangle, then I would probably recursively define it and calculate it that way. (Pascal's formula shows that each subsequent row is obtained by adding the two entries diagonally above) Instead of constantly calculating it at each position with n choose k.
I guess you could use the binomial coefficient definition and memoize the choose and factorial. Memoization alone is what is saving you here. Luckily arc provides this functionality.
Anyways, this is a fun problem. Much easier to solve elegant and efficiently in arc, thanks to memoize. Try this in an imperative language and you'll definitely have to fall back on the recursive definition because all those factorials and chooses will kill the performance. There is one other benefit to using the recursive definition - you won't use any extra memory memoizing factorials. Instead you'll just have the chooses appearing in the tree.
A bit nit picky, but memoization alone won't make the solution optimal, since you are dealing with very large numbers. n! has O(n log n) digits, so in the limit it will take O(n log n) time just to calculate n! from n * (n-1)!.
But I don't know about your big-O estimate. Since the triangle is constructive and you are memoizing calculating n! from n * (n - 1)! will take O(1). It'll be the cached (n - 1)! value times n.
Doing a single multiplication is not O(1) when the numbers have more than a constant number of digits. I'm not precisely sure how long multiplying large numbers takes, but it's at least linear in the number of digits involved. And (n-1)! has O(n log n) digits.
No prob. Sorry if I go on at too much length here ;-)
So a useful formula for counting digits is, a positive integer x has floor(log10(x)) + 1 digits. You can figure this out yourself by thinking, where does the digit-counting function bump up a notch? At 10, 100, 1000, etc. So asymptotically the number of digits in x is O(log x).
So n! has O(log n!) digits. The trickier part is figuring out or knowing that O(n log n) = O(log n!). Using log ab = log a + log b you can expand out the factorial:
In case the last step isn't clear, you can do this splitting-in-half bounding trick. Since each element in the sum is less than log n you can bound from above with
log n + log (n-1) + ... + log 2 + log 1 < n log n
And if you just take the larger half of the list you can bound from below with
Usually, it seems to be either (n log n) or (n log n) - 1 digits.
And usually in this case I would leave of the O, as that usually refers to the performance of an algorithm in time or space. I suppose you could construe the number of digits to be "space" but multiplying O(n) numbers doesn't make that much sense.
