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.

  • 3
    $\begingroup$ more help in cs.stackexchange.com/questions/824/… $\endgroup$ – Ran G. Oct 6 '15 at 1:09
  • $\begingroup$ Neither question you've given is related at all. Sorry. $\endgroup$ – Jared Oct 6 '15 at 1:15
  • 1
    $\begingroup$ I'm not sure I get you. You understand the meaning of, say, $O(2^n)$ but you don't know how to prove whether or not $2^{n+1} =O(2^n)$? To me it seems you still don't understand the meaning of $O$, $\Omega$, etc. Maybe try to be more specific, so we could help. $\endgroup$ – Ran G. Oct 6 '15 at 1:47
  • $\begingroup$ The third question you've posted looks hopeful and I'm reading through it, thank you. I understand that 2^(n+1)=O(2^n) means that the function has a runtime of "at worst, 2^n" meaning that the upper-bound of the runtime curve would be the function y=2^x. However, I don't understand what goes in to proving this statement. I've never written a proof in my life, and the format of the proofs that I've seen intimidate me. I don't know what writing one entails, and I don't think I've been equipped to write one myself and be confident that it is correct. $\endgroup$ – Jared Oct 6 '15 at 1:52
  • $\begingroup$ Still don't get your question, but maybe cs.stackexchange.com//questions/192/… is what you are missing. $\endgroup$ – Ran G. Oct 6 '15 at 1:58

Browse other questions tagged or ask your own question.