GATE CSE 1992 | Question: 07b

Question

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. Solve the recurrence relation for a closed form solution of $F(n)$.

Comments

part a

https://gateoverflow.in/586/gate1992-07a

Answer 1

Function F(n)
begin
F1 ← 1
if(n=1) then F ← 3  //if (n==1) then return 3 
 else
   For i = 1 to n do
        begin
            C ← 0
           For j = 1 to n – 1 do //inner loop runs n-1 times outer loop runs for n times 
           begin C ← C + 1 end   //means C=n-1
           F1 = F1 * C  //means n-1 is getting multiplied n times so ans is (n-1)^n for n>=2 
       end 
    F = F1 
end

Comments

got it

---

How can we say that 

 F = F1

is related to else and not to the main begin end?

---

@Rajesh

Can u chk this one plz

C is incrementing each time,

then how (n-1) is multipling n times?

---

@Srestha,inner loop will go from 0 to n-1 and will increment c.So will have n-1.So inner loop is doing nothing but assigning n-1 to c.Now we multiply n-1*1 for first iteration.And outer loop is running n times.so everytime c get n-1 and this n-1(c) is multiplied with previous f1 which is n-1 itself so now we get n-1*n-1 and so on.outer loop goes n times and inside it multiply n-1 with f1

---

this program is not recursive, how can we write and solve recurrence relation for it?

---

Yeah same thing and its definitely not possible.

They suppose to write the kind of formula.

Answer 2

F(n) = (n-1)ⁿ    When n>=2

F(n) = 3  When n == 1

Comments

i think it would be o(n^2)

---

here ask about close form.

Solve the recurrence relation for a closed form solution