Properly Solving a Big-O Proof [closed]

Closed. This question is off-topic. It is not currently accepting answers.

---

Want to improv开发者_StackOverflow中文版e this question? Update the question so it's on-topic for Stack Overflow.

Closed 12 years ago.

Improve this question

I am currently taking a class which is incorporating a topic I have not yet had much experience with - Big-O. Here is an example of the type of questions I will need to answer. Please note: these questions resemble that of those which I will need to do for homework, however, the numbers, etc. are changed.

I am not looking for solutions. I am looking for an explanation on how to effectively write the proof up.

The problems look like this (the first equation is f(n) the second is g(n)):

(a) 5^(log_5(n)) and 3n+2
(b) n^2 and sqrt(3)^(log(n))

I understand that, to effectively write the proof, I must prove that

|f(x)| <= c|g(x)| for all x >= k

(k == n_0 depending on how you were taught) So for the first one I simplify the question to

n is O(3n+2)

and I'm not entirely certain how to begin the second one.

From here, how do I pick values c and k? Are they simply arbitrary values which just make the equation true or is there something more which I am missing? I have seen many examples, but none of these explain how they are getting their values for c and k.

Thanks for your help!

---

Remember what the purpose of big-O is anyway: you are trying to show that a function grows, with large enough inputs, at a rate no "faster" than a certain other function (its upper bound). With that in mind, k can be fairly arbitrary, but you probably want to choose the smallest non-negative value of k for which the inequality holds. If you can't find a definite smallest k, choose one that works. Also, since we typically "throw out" constants on the most significant term of the upper bound, similarly, choose the smallest positive c for which the inequality holds. Again, if you can't determine a "smallest," just choose one that works. Once you recall what k and c represent, it isn't too hard to remember that this is what to do with them.

Your teacher/professor may have different ideas, so you'll probably wish to double-check, but this is pretty much what this particular music-major-who-took-some-graduate-comp-sci remembers from Algorithms class.

Hope that helps!