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

  • 1
    $\begingroup$ Many textbooks will describe the necessary prerequisites in their introduction. Have you tried looking there? (Book suggestions/recommendations are off-topic for this site. See the help center.) $\endgroup$ – D.W. Oct 6 '14 at 4:27

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.

  • $\begingroup$ In algorithms and complexity we use calculus mostly to estimate sums and to compute first-order (or more) approximations. Sometimes you see more advanced stuff such as differential equations, but that's rare. One of my papers uses integration by parts at some point, but this is also not very typical $\endgroup$ – Yuval Filmus Oct 6 '14 at 5:08
  • $\begingroup$ As for mathematical maturity, it's hard to define; you (hopefully) obtain it after sufficient active exposure to (proof-based) math. In a sense, it is multi-levelled, and people working in algorithms and complexity typically don't reach the same level of maturity as algebraic geometers, say. $\endgroup$ – Yuval Filmus Oct 6 '14 at 5:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.