I'm taking my first algorithms class, and the first exam is tomorrow. I've been looking forward to this class since freshman year, but now that I'm in it the professor is less than stellar and I've been having trouble (making tomorrow's exam worrying). We've covered the meaning of each of the notations, but we'll be asked on the exam questions like:
- Prove max(f, g) = Θ(f + g)
- Prove (n + a)^b = Θ(n^b)
- Is 2^(n+1) = O(2^n)?
I've never worked with these kinds of proofs before. I've been trying to look these problems up on a case-by-case basis, but I've realized that's a terrible idea. What my professor's failed to reasonably explain in class is how to actually approach these kinds of problems. Could someone help explain to me as simply as possible how to approach these so that I can handle any type of proof like this in the future?
Edit: This isn't a duplicate of the suggested question at all. I am not asking of the meaning of the given notations, the growth rates or certain function types, or which one to use at all. I am asking how to prove that a given specific function has a certain complexity.