TF The recursive definition for the factorial function is f(n) nf(n-1), and f(1)

Question

TF The recursive definition for the factorial function is f(n) nf(n-1), and f(1) 1 T F Let a be 1 plus the last digit of your student ID. Iff. Z- Z and f(x)- x/a)+13x/al + (x mod a)+ x!, then f(5)-13 Consider an application whose runtime can be expressed as f(n) = f(n-1)-n, where f(1) is 1 plus the first digit of your student ID. Then, the running time of f is O(log n). F Consider an application whose runtime can be expressed as f(n) = f(n-1)-n, where f(1) is 1 plus the second digit of your student ID. Then, the running time of f is O(n). T F

Explanation / Answer

1)

True.

The recursive definition for factorial is f9n) = n*f(n-1)
and the base/termination condition is f(1) = 1

2)

False

Given f(x) = floor[x/a] + ceil[3x/a] + (x mod a) + x!

Let the last digit of your student id is 'p'

Hence a = (1+p) > 0

But, f(5) = floor[5/a] + ceil[15/a] + (5 mod a) + 5!
= 120 + floor[5/a] + ceil[15/a] + (5 mod a) (Since 5! = 120)
Hence f(5) > 120
Therefore f(5) not equal to 13.

3)

False

Let the first digit of your student id is 'id'

Hence f(1) = (1+id)

Given, recurrence relation is

f(n) = f(n-1) - n

n=1 => f(1) = f(0) - 1   
But f(1) = 1+ id
=> f(0) - 1 = 1+id => f(0) = 2+id

n=2

f(2) = f(1) - 2
= 1+id -2
= id-1

n=3

f(3) = f(2) - 3
= (id-1) - 3
= id-4

Since id is a digit , 0<= id<=9

Hence , maximum value of a function can be (1+id) = 10

Hence, In the initial stages , for n<=100, the following equation may not hold. But for large inputs such as n>100, f(n) = O(log n)

But in general to know f(n), you have to go back to f(0) which is traversing the function 'n' times. Hence f(n) = O(n) for all inputs

Hence, f(n) = O(n)

4)
True

Same as above

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.