Suppose that f(n) satisﬁes the divide-and-conquer relation $$f ( n ) = 2 f ( n / 3 ) + 5 \text { and } f ( 1 ) = 7$$ What is f(81)?

Name: Suppose that f(n) satisﬁes the divide-and-conquer relation \[f ( n ) = 2 f ( n / 3 ) + 5 \text { and } f ( 1 ) = 7\] What is f(81)?
Brand: Quizplus
Rating: 4.7 (27 reviews)

Question

Quizplus · Accepted Answer

The Answer is Using the recurrence relation repeatedly, and simplifying when possible, we find that

f ( 81 ) = 2 \cdot f ( 27 ) + 5 =

2 \cdot ( 2 \cdot f ( 9 ) + 5 ) + 5 = 4 \cdot f ( 9 ) + 15 = 4 \cdot ( 2 \cdot f ( 3 ) + 5 ) + 15 = 8 \cdot f ( 3 ) + 35 = 8 \cdot ( 2 \cdot f ( 1 ) + 5 ) + 35 = 16 \cdot f ( 1 ) + 75 =

16 \cdot 7 + 75 = 187

.

Suppose That F(n) Satisﬁes the Divide-And-Conquer Relation f(n)=2f(n/3)+5 and f(1)=7f ( n ) = 2 f ( n / 3 ) + 5 \text { and } f ( 1 ) = 7f(n)=2f(n/3)+5 and f(1)=7

Suppose That F(n) Satisﬁes the Divide-And-Conquer Relation $f ( n ) = 2 f ( n / 3 ) + 5 \text { and } f ( 1 ) = 7$