You are given a n x n grid. Each grid intersection point can be located using row and column indices. Take a look at the color pattern for n = 5.

 

Your are provided with the following function to color a triangle specified by vertices paint (color, (i, j), (k, 1), Cm, n)) will paint the triangle made out of (i, j), (k, 1) and (m, n) vertices with the color, color.

Example: paint (red, (2, 2) (3, 2) (3, 3)) was used to color the above triangle in 5 x 5 grid.

(a) Write an algorithm, CoLORGRID(A), to paint n x n grid according to above color pattern. 

(b) Analyze the running time of the algorithm and justify your answer. Note: Do not write Java code. Pseudo code only!

2 3 4 5 Red Red Red Red Blue Blue Blue Blue 2 Red Red Red Blue Blue Blue Blue 3. Red Red Red Red Blue Blue Blue Blue Red Red Red Red Blue Blue Blue 5 Blue