2
$\begingroup$

$f(0) = 3$

$f(1) = 3$

$f(n) = f(\lfloor n/2\rfloor)+f(\lfloor n/4\rfloor)+cn$

Intuitively it feels like O(n), meaning somewhat linear with steeper slope than c, but I have forgot enough math to not be able to prove it...

2 Answers 2