The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+6 votes
631 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)$

asked in Algorithms by Veteran (59.6k points)
edited by | 631 views

4 Answers

+19 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$

answered by Boss (20.7k points)
edited by
+1
wah pragy sir maza aa gaya
+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
 

answered by Veteran (101k points)
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}$
answered by Boss (26k points)
+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.
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}$
answered by (255 points)

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

42,658 questions
48,639 answers
156,218 comments
63,953 users