- #1
ramenmeal
- 4
- 0
Homework Statement
Find f(n) when n = 2^k, where f satisfies the recurrence realtion f(n) = f(n/2) +1 with f(1) = 1
Homework Equations
f(n) = a*f(n/b) + c
when n = b^k, where k is a positive integer,
f(n) = C1n^(log a base b) + C2
C1 = f(1) +c/( a-1) and C2 = -c/ (a-1)
keep in mind i may be trying to use the wrong equation...
The Attempt at a Solution
a =1, b = 2, c = 1
then C1 = 1+ 1/0 and C2 = -1/0
i'm not sure what i can do from here... c1 and c2 both include undefined #'s
perhaps I'm not even approaching the problem correctly?