Unpacking the Master Theorem: Understanding its Proof and Cases

[evinda]

Hello! (Wave)

View attachment 4431

View attachment 4432View attachment 4433

View attachment 4434

Do you have an idea how we could prove the above theorem?

The proof has to be iterative.

 

[evinda]

Now I found the following proof:

View attachment 4435

Don't we have to explain further which case correponds to which of the following cases

• The first term is dominant.
• Each part of the summation is equally dominant.
• The summation is a geometric series

and justify why it is like that? (Thinking)