1
$\begingroup$

Let $f$ be a positive function such that $$f(n) = a f\left( \left\lfloor \frac nb\right\rfloor\right) + c$$ holds for every integer n ≥ 1, where a ≥ 1, b is an integer larger than one, and c ∈ R+ .

Prove that $f(n) = O(n^{\log_b a})$ if a > 1, and $f(n) = O(\ln n)$ if a = 1

I don't understand where to begin, I tried using the formal definition of big O notation but still couldn't progress any further

$\endgroup$
1
  • $\begingroup$ Please clarify your specific problem or provide additional details to highlight exactly what you need. As it's currently written, it's hard to tell exactly what you're asking. $\endgroup$
    – Community Bot
    Commented Feb 27, 2023 at 7:29

1 Answer 1

Reset to default
2
$\begingroup$

You may want to have a look at some proofs of the Master Theorem as your question seems extremely similar.

$\endgroup$
1
  • $\begingroup$ got it, thanks! $\endgroup$
    – Hazardous Joe
    Commented Feb 28, 2023 at 13:52

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .