[Solved]: Prerequisites of computational complexity theory

Problem Detail: 

what's the prerequisite topics needed for understanding computational complexity theory and analysis of algorithm ...including big-O and Big-theta notations and these staff. I want a mathematical background and good book suggestions for each topic ... thanks

Asked By : Eng_Boody

Answered By : Yuval Filmus

Here are some prerequisites:

1. Mathematical maturity. You get this by taking math courses.
2. Mathematical induction. Important.
3. Rudimentary calculus. That also includes all you need to know about big O notation, which you can learn as part of your study of algorithms and complexity. Calculus is mainly used for estimating sums and in general asymptotic analysis.
4. Rudimentary linear algebra. Not relevant for everything, but common enough.
5. Basic discrete probability theory (linearity of expectation, Markov's and Chebyshev's inequalities, Bernoulli random variable, binomial distribution, indicator variables). Very helpful. Part of it (Chernoff's bound) you will learn as part of your study.
6. Basic graph theory. Most people probably don't actually have any background in graph theory to begin with, and learn whatever they need as part of their algorithms course.

Since calculus and linear algebra are common enough, what is probably most challenging is discrete probability theory. There are many textbooks covering this, and probably all of them are fine. Whatever you don't learn ahead of time you will pick up in your algorithms and complexity classes.

On the other hand, it is important to be proficient in induction and arithmetic manipulations, and to have some basic level of mathematical maturity. The only way to achieve this is to gather experience in doing basic proof-based math.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/30631