Recursive Pascal's Triangle Row big O cost

Question

I'm studying for CS interviews and I decided to try making up my own problem and solving it recursively.

The question I am trying to solve is this: I want to be able to write a recursive function that finds the nth row of pascal's triangle.

Ex pascals(1) -> 1
   pascals(2) -> 1,1
   pascals(3) -> 1,2,1

I believe I have solved this function. It takes a helper function to get it started with the base case.

function int[] nthPascal(int[] a, int n){
  // in the case that the row has been reached return the completed array
  if(n==1){
    return a;
  }
  // each new row of pascal's triangle is 1 element larger. Ex 1, 11, 121,1331 etc. 
  int[] newA = new int[a.length()+1];

  //set the ends. Technically this will always be 1.
  // I thought it looked cleaner to do it this way. 
  newA[0]=a[0];

  newA[newA.length-1]=a[a.length-1];

  //so I loop through the new array and add the elements to find the value.
  //ex 1,1 -> -,2,- The ends of the array are already filled above
  for(int i=1; i<a.length; i++){

    // ex 1+1 = 2 for 1,1 -> 1,2,1
    newA[i]=a[i-1]+a[i]
  }
  //call the recursive function if we are not at the desired level
  return nthPascal(newA,n-1);
}

/**
*The helper function
*/
public int[] helperPascal(int n){
  return nthPascal(int[] {1},n);
}

My question is how do I find the bigO cost?

I am familiar with common algorithm costs and how to find them. The recursion in this makes it confusing for me.

I know it's clearly not constant, n, nlogn, etc. My thought was that it was 3^n?

I searched for an example and found: Pascal's Triangle Row Sequence and What is the runtime of this algorithm? (Recursive Pascal's triangle). But they are trying to find a specific element in a given location I believe. I couldn't find anyone implementing pascal's triangle this way and talking about bigO cost.

Is this because there is a better way to write a recursive row finding pascal's function? If so please share :)

Answer 1

Each time you call nthPascal, it calls itself recursively just once. Therefore, you can get the time complexity by adding the time complexities of each invocation of the function (excluding the recursive call). (If you had a function that traverses a binary tree, it would typically call itself recursively twice, which makes the computation more complicated. Here, though, since it calls itself only once, the computation is pretty simple.)

Each invocation of the function has a loop that executes a.length times, and the body of the loop executes in constant time. There aren't any other loops or any other statements that execute in anything but constant time, except for when you allocate the array intA because Java will intialize every element of the array. The result, though, is that when you call nthPascal with an array of length M, the execution time will be O(M) not counting the recursive call.

So assuming that the execution time is roughly M*k for some constant k, that means the total execution time will be 1*k + 2*k + 3*k + ... + (n-1)*k. And 1 + 2 + 3 + ... + n - 1 is (n * (n - 1)) / 2, which is O(n²). So O(n²) is the answer you're looking for.

Answer 2

For each recursive call, you are doing a for loop of size k, where k is the depth of the recursive call (at depth k, you have an array of size k).

To get the complete row at depth n, you call nthPascal at depth 1, 2, ..., n.

Therefore, your total complexity will be 1+2+...+n=n(n+1)/2 = O(n²).