Algorithm to efficiently determine the [n][n] element in a matrix

This is a question regarding a piece of coursework so would rather you didn't fully answer the question but rather give tips to improve the run time complexity of my current algorithm.

I have been given the following information:

A function g(n) is given by g(n) = f(n,n) where f may be defined recursively by

I have implemented this algorithm recursively with the following code:

public static double f(int i, int j) 
{

    if (i == 0 && j == 0) {
        return 0;
    }
    if (i ==0 || j == 0) {
        return 1;
    }

    return ((f(i-1, j)) + (f(i-1, j-1)) + (f(i, j-1)))/3;
}

This algorithm gives the results I am looking for, but it is extremely inefficient and I am now tasked to improve the run time complexity.

I wrote an algorithm to create an n*n matrix and it then computes every element up to the [n][n] element in which it then returns the [n][n] element, for example f(1,1) would return 0.6 recurring. The [n][n] element is 0.6 recurring because it is the result of (1+0+1)/3.

I have also created a spreadsheet of the result from f(0,0) to f(7,7) which can be seen below:

Now although this is much faster than my recursive algorithm, it has a huge overhead of creating a n*n matrix.

Any suggestions to how I can improve this algorithm will be greatly appreciated!

I can now see that is it possible to make the algorithm O(n) complexity, but is it possible to work out the result without creating a [n][n] 2D array?