edited by
2,275 views
13 votes
13 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. Solve the recurrence relation for a closed form solution of $F(n)$.
edited by

2 Answers

Best answer
14 votes
14 votes
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
selected by
9 votes
9 votes

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

F(n) = 3  When n == 1

Related questions

23 votes
23 votes
3 answers
3
Kathleen asked Sep 13, 2014
4,552 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,308 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 ...