Question

For the following recurrence, provide an asymptotic characterization.
f(n) = f(n/3) + 1

Answer 1

There is no base case

Answer 2

Unfortunately, we aren't given a base case. It does say, however, that we need not prove them, if that makes a difference.

Answer 3

I'd say that it's like a Big-O characterization of a linear function, but I'm not sure if I'm even doing this part correctly.

Answer 4

\[
f(n) = f(n/3)+1 = f(n/3^2)+2=f(n/3^3)+3 = f(n/3^{\log_3n})+\log_3 n = f_0+\log_3n
\]

Answer 5

Or make that \(f_1\). I'm assuming it stops at \(1\), otherwise it would go on forever.

Answer 6

Alright, would you care to elaborate on how you got that equation?

Answer 7

...you don't see the pattern?

Answer 8

\(3^{\log_3 n }=n\)

Answer 9

Sorry, it's really hard to read those exponents.

Answer 10

Ok, zoomed in 150% now, and I can read the exponents.

Answer 11

\[
f(n) = f(n/3)+1 = (f((n/3)/3) + 1) + 1 = f(n/3^2)+2 =f(n/3^k)+k
\]

Answer 12

Ok, I think I'm getting this.

Answer 13

So, if I were to throw a constant, like 2 or 4 in front of the f(n/3), would that change anything? Or would I just throw it in front of the answer we got?

Answer 14

try for yourself

Answer 15

\[
f(n) = af(n/b) + c
\]

Answer 16

Ok, I'll give this a go in the morning. Thank you a ton!