edited by
3,493 views
15 votes
15 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)$.
edited by

4 Answers

Best answer
39 votes
39 votes
  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
2 votes
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
 

1 votes
1 votes
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}$
0 votes
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

23 votes
23 votes
3 answers
3
Kathleen asked Sep 13, 2014
4,549 views
Assume that the last element of the set is used as partition element in Quicksort. If $n$ distinct elements from the set $\left[1\dots n\right]$ are to be sorted, give an...
9 votes
9 votes
3 answers
4
Kathleen asked Sep 12, 2014
7,300 views
Which of the following problems is not $\text{NP}$-hard?Hamiltonian circuit problemThe $0/1$ Knapsack problemFinding bi-connected components of a graphThe graph coloring ...