Pascal's Triangle Algorithm Analysis

Question

Do you think the pseudocode below is correct for calculating pascal's triangle? What would its time and space complexity be like? and how can I calculate it?

pascal triangle(n){
    list<list<int>> triangle // double list saving the triangle




    triangle.get(0).add(1)
    for(int i=1; i<n; i++){
        for(int j=0; j<i; j++){
            if(triangle.get(i-1).get(j)==null || triangle.get(i-1).get(j-1)==null)  
                triangle.get(i).add(1)
            else
                triangle.get(i-1).add(triangle.get(i-1).get(j)+triangle.get(i-1).get(j-1))

        }

    }

    print(triangle)
}

Answer 1

Your pseudocode looks like it makes sense.

For the complexity

Your algorithm is trying to calculate each number of the triangle once. If we let each calculation be constant time complexity then we are doing:

sum(i) (0 -> n)

Please excuse the poor notation To clarify:

If n is 6 then we are going to iterate 6 + 5 + 4 + 3 + 2 + 1 times. This actual complexity can be simplified to:

(n + 1) * (n/2)

effectively

O(n^2)

Another way of looking at the complexity

You are essentially doing the area of a triangle in iterations which is b*h/2. Well we know the height of Pascal's triangle to be n. The bottom of the triangle (or the base) has n numbers. Therefore, we are generating:

n^2/2

which has a complexity of O(n^2)