wah pragy sir maza aa gaya

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+8 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]

(a) Derive a recurrence relation for $F(n)$

+20 votes

Best answer

- The function $F(n)$ is NOT a recursive function. You can't have a recurrence relation for it in the first place!
- $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$

+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

a_{n} = ((n-1) a_{n-1})^{n} +2

- All categories
- General Aptitude 1.5k
- Engineering Mathematics 7.1k
- Digital Logic 2.7k
- Programming & DS 4.9k
- Algorithms 4.2k
- Theory of Computation 5.3k
- Compiler Design 2.1k
- Databases 4k
- CO & Architecture 3.5k
- Computer Networks 4k
- Non GATE 1.4k
- Others 1.5k
- Admissions 556
- Exam Queries 553
- Tier 1 Placement Questions 23
- Job Queries 69
- Projects 18

47,903 questions

52,285 answers

182,209 comments

67,715 users