Pascal Triangle c# code space complexity

Question

can you give me your impression of my implementation of Pascal triangle problem? I'm especially interested in space complexity evaluation thank you all!

public List<List<int>> generate(int A)
{
 List<List<int>> result = new List<List<int>>();
 int currenctRowLength = 1;
 List<int> previousRow = new List<int>();
 for (int i = 0; i < A; i++)
 {
 List<int> row = new List<int>();
 row.Add(1);
 currenctRowLength = i + 1;
 int j = 1;
 while (j < currenctRowLength - 1)
 {
 row.Add(previousRow[j] + previousRow[j - 1]);
 j++;
 }
 if (i > 0)
 {
 row.Add(1);
 } 
 previousRow=row;
 result.Add(row);
 }
 return result;
}

• greybeard: (Welcome to CR!) space complexity reads asymptotic analysis to me: what operations are to be supported with what constraints satisfied? My take: don't fret about ("per item") storage required(yet): if it takes more space than you are willing to pay, it will be taxing your patience in the first place.
• greybeard: (my implementation of [a] problem reads funny.)
• Luke: I was wondering if there is a better solution, I guess there is.
• greybeard: You didn't edit into your code/question what interface the result is to support - IList<IList<ulong>>pascalTriangle() would open up a lot of possibilities List<List<int>>(int) obstructs. (Note: it wouldn't even need a numberOfRows parameter (what the hell is A?))
• Luke: I agree but in this case the return type was fixed

Answer 1

As I think greybeard was trying to say, unless you are know that memory consumption/allocation costs are a serious concern, then this code is fine from a memory point of view. The space-complexity is the same as the output (quadratic in A), so you can't do better than that.

There a couple of small things to be said:

• as GreyBeard says, A is completely meaningless, and should really have a lowerCamelCase name as a parameter (e.g. dimension, size?); generate ought to be GeneratePascalTriangle or something meaningful (public -> UpperCamelCase) (msdn reference)

• currenctRowLength should be currentRowLength, and should only be defined inside the for loop (i.e. where it is assigned); I like that this is its own variable.

• you are using a while loop over j, when a for could be more readable (simply because people are used to reading for-loops), and doesn't leak j into the outer scope.

• List<List<int>> is a pretty horrid type to be returning: much better to have IReadOnlyList<IReadOnlyList<T>> if the return value is meant to be immutable (which is assignable from List<List<T>> or T[][]).

• I'd be inclined to initialise previousRow to null, rather than an empty list: it isn't read until i == 2; assigning it to a 'meaningful' value is defensive and only can work to obscure bugs in the rest of the code.

Mindless Performance Musing

If memory usage/allocations/GC hammering is a real concern, then you can improve matters by not using resizing lists. You havn't given us any idea of what the code is actually meant to do, so it's a bit hard to suggest an alternative, but you could either use arrays (which obvious are non-dynamic) or you can preserve the signature by creating lists with a given initial capacity with the .ctor(int) overload. Note that this will give a performance benefit, but change the time-complexity (which is also quadratic in A).

Code

Putting all of that together (and using arrays instead of lists, because mindless performance is fun, and I don't think it harms the readability here much):

/// <summary>
/// Generates a pascal triangle with the given number of rows
/// </summary>
public static IReadOnlyList<IReadOnlyList<int>> GeneratePascalTriangle(int numberOfRows)
{
 int[][] result = new int[numberOfRows][];
 int[] previousRow = null;
 for (int i = 0; i < numberOfRows; i++)
 {
 int currentRowLength = i + 1;
 int[] row = new int[currentRowLength];
 result[i] = row;
 // start and end
 row[0] = 1;
 row[currentRowLength - 1] = 1;
 // middle
 for (int j = 1; j < currentRowLength - 1; j++)
 {
 row[j] = previousRow[j] + previousRow[j - 1];
 } 
 previousRow = row;
 }
 return result;
}