in Algorithms edited by
2,114 views
12 votes

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]

  1. Derive a recurrence relation for $F(n)$.
in Algorithms edited by
2.1k views

1 comment

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

https://gateoverflow.in/43600/

0

Subscribe to GO Classes for GATE CSE 2022

4 Answers

33 votes
 
Best answer
  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$

edited by

4 Comments

wah pragy sir maza aa gaya
2
Sir your answer is correct for n>1. For n=1, it is 3 which is not equal to (n-1)^n
0
Can anyone check this code with $\mathrm n = 5$ because I am getting answer $72$ and which is $\ne \left ( n-1\right )^n$
1
I checked. It’s $(n-1)^n$.
0
2 votes

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!)4 as answer

Recurrence relation will be

an = ((n-1) an-1)n +2
 

2 Comments

Why You have added 2  ??
see F(1)= 1, F(2)= 1, F(3)= (2!)^3
0
@srestha can you explain it more clearly how 3! came
0
1 vote
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}$

2 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
6
Thanks @Pragy  , I did not notice that.
2
0 votes
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}$

Related questions