I know this question goes a way back and there are some excellent answers here, nonetheless I wanted to share another bit forFor the mathematically-minded people that will stumble in this post.: The Master theoremmaster theorem is another usefulluseful thing to know when studying complexity. I didn't see it mentioned in the other answers.
Active reading [<https://en.wikipedia.org/wiki/Master_theorem_(analysis_of_algorithms)> <https://en.wiktionary.org/wiki/useful#Adjective>]. Removed meta information (this belongs in comments).
Peter Mortensen
- 31.4k
- 22
- 110
- 134