Consider the following pseudo-code:

// Assume i, j, k are integers

for i = 1 to n do

for j = n-i+1 to n {

k = 1;

while (k*k <= j)

{ perform ;

k = k + 1; } }

Find an expression for f(n), the number of times is performed. Find g(n) so that f(n) is (g(n)). Prove your answer.