GATE CSE 1992 | Question: 07a

Question

Consider the function $F(n)$ for which the pseudocode is given below :

Function F(n)
begin
F1 ← 1
if(n=1) then F ← 3
 else
   For i = 1 to n do
        begin
            C ← 0
           For j = 1 to n – 1 do
           begin C ← C + 1 end
           F1 = F1 * C
       end
 F = F1
end

[$n$ is a positive integer greater than zero]

• A. Derive a recurrence relation for $F(n)$.

Comments

Can anyone tell what is the difference between these two questions. both looks same apparantely…

https://gateoverflow.in/43600/

---

in Q 7a we have to write recurrence relation and in Q7b we have to fin the value of recurrence relation at some general variable n

 

Answer 1

1. The function $F(n)$ is NOT a recursive function. You can't have a recurrence relation for it in the first place!
2. $F(n)$ calculates $(n-1)^n$.

The equivalent C++ code is as follows: (You can try it out here: http://ideone.com/w0u4lk)

long F(long n) {
	long F1 = 1;
 
	if(n==1) { return 3; }
	else {
		for(long i = 1; i <= n; i++) {
			long C = 0;
			// Note: the belore For loop only has one line
			for(long j = 1; j <= n-1; j++) { C = C+1; }
			// At the end of this for loop, C will be = (n-1)
			F1 = F1 * C;
		}
	}
	return F1;
}

It is clear that the inner for loop can be replaced by a single statement as follows:

long F(long n) {
	long F1 = 1;
 
	if(n==1) { return 3; }
	else {
		for(long i = 1; i <= n; i++)
			F1 = F1 * (n-1);
	}
	return F1;
}

And this calculates $(n-1)^n$

Comments

I checked. It’s $(n-1)^n$.

---

`JEET sir 

It is correct. for n=5  we get  4^5.

---

Solving recurrence relation without recursion: https://stackoverflow.com/questions/30201391/how-to-write-a-recurrence-relation-for-a-given-piece-of-code

Answer 2

The program is giving factorial upto (n-1) numbers

here are two "for" loops

But each time i value increments C initialized to 0 again

Say i=4 and j=3

it will give (3!)⁴ as answer

Recurrence relation will be

a_n = ((n-1) a_n-1)ⁿ +2
 

Comments

Why You have added 2  ??
see F(1)= 1, F(2)= 1, F(3)= (2!)^3

---

@srestha can you explain it more clearly how 3! came

Answer 3

Inner loop is giving factorial of (n-1).
And outer loop is multiplying the same (n-1)! to n times.

F(n) = $\begin{cases} 1 & \text{ if } n= 1\\ ( (n-1)F(n-1))^{n}& \text{ if } n >1 \end{cases}$

Comments

Notice where the inner loop begins and ends.

begin C ← C + 1 end

The following line is outside the inner loop

F1 = F1 * C

---

Thanks @Pragy  , I did not notice that.

Answer 4

I think there is a recurrence relation for this function.

$f(i) = f(i-1)*(n-1)$ provided $i\geq2$ and $f(1)=1$ which gives $f(n)=(n-1)^{n}$