728 views

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)$

edited | 728 views

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
+1
wah pragy sir maza aa gaya
0
Sir your answer is correct for n>1. For n=1, it is 3 which is not equal to (n-1)^n

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

0
Why You have added 2  ??
see F(1)= 1, F(2)= 1, F(3)= (2!)^3
+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}$
+5

Notice where the inner loop begins and ends.

begin C ← C + 1 end

The following line is outside the inner loop

F1 = F1 * C
+2
Thanks @Pragy  , I did not notice that.
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}$

1
2
+1 vote