The Master Method Case


### Proof is on [Introduction to Algorithm](https://texonom.com/introduction-to-algorithm-e7e86c2968934959b53c2c2160bec4c6) 
proof is easy to understand
![](https://www.notion.so/image/https%3A%2F%2Fprod-files-secure.s3.us-west-2.amazonaws.com%2F0bf522c6-2468-4c71-99e3-68f5a25d4225%2Faee544bb-0bbc-4756-82ec-888ec58cee19%2FUntitled.png?table=block&id=31d702c1-ce01-45df-9c17-160f8d038702&cache=v2)
![](https://www.notion.so/image/https%3A%2F%2Fprod-files-secure.s3.us-west-2.amazonaws.com%2F0bf522c6-2468-4c71-99e3-68f5a25d4225%2Fa7dc6a24-54b1-4a4a-bfb8-6e272ad7605b%2FUntitled.png?table=block&id=f0847bdd-c435-478d-832f-8fa609b46c02&cache=v2)



if $f(n)$ does not meet regularity condition, you can’t use the master theorem in the third case



### Example
![](https://www.notion.so/image/https%3A%2F%2Fprod-files-secure.s3.us-west-2.amazonaws.com%2F0bf522c6-2468-4c71-99e3-68f5a25d4225%2F43a55351-d727-4e4e-9852-a77f7764484c%2FUntitled.png?table=block&id=58c45eb6-fb81-4880-80aa-4847772f8caa&cache=v2)




> [Master theorem (analysis of algorithms)](https://en.wikipedia.org/wiki/Master_theorem_(analysis_of_algorithms))





